Posts Tagged ‘spigot’

Programming Praxis – Digits Of E

June 19, 2012

In today’s Programming Praxis exercise, our goal is to implement two algorithms to calculate the digits of e using a spigot algorithm: one bounded and one unbounded version. My solution for the unbounded version is already posted in the exercise itself, so I’ll only cover the bounded version here. Let’s get started, shall we?

A quick import:

import Data.List

The main trick used for the whole carry and modulo stuff is the use of mapAccumR; it allows us to produce a list of the modulos while also producing the resulting digit. Other than that, the implementation is straightforward: call the function n-1 times with an initial argument of n+1 ones and tack a 2 on the front.

spigot_e :: Int -> [Int]
spigot_e n = 2 : take (n - 1) (f $ replicate (n + 1) 1) where
    f = (\(d,xs) -> d : f xs) .
        mapAccumR (\a (i,x) -> divMod (10*x+a) i) 0 . zip [2..]

A test to see if everything is working properly:

main :: IO ()
main = print $ spigot_e 30