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

Question

I'm trying to find the first 100,000 binary digits in the expansion of 'e'. Is there an algorithm to generate the binary digits of 'e' as a infinite list?

Answer 1

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.