how to generate a series representing the binary expansion of 'e'

algorithm, clojure, haskell, lazy-evaluation

Solution

Here's an unbounded spigot for `e` in Haskell:

main = print $ stream (1,0,1) [(n, a*d, d) | (n,d,a) <- map f [1..]]
    where
        f k = (1, k, 1)

stream z (x:xs)
    | lbound == approx z 2 = lbound : stream (mul (10, -10*lbound, 1) z) (x:xs)
    | otherwise            =          stream (mul z x) xs
  where
    lbound = approx z 1

approx (a,b,c) n = (a*n + b) `div` c

mul (a,b,c) (d,e,f) = (a*d, a*e + b*f, c*f)

Based on the Programming Praxis unbounded spigot for e and pi, which in turn is derived from Gibbon's first unbounded spigot for pi.

$ runhaskell A.hs
[2,7,1,8,2,8,1,8,2,8,4,5,9,0,4,5,2,3,5,3,6, ^C

I'd recommend Gibbon's paper if you're interested in these fun algorithms.

Problem

Original source

Related problems

• Code to Generate e one Digit at a Time