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?

See this question: http://stackoverflow.com/questions/9144154/code-to-generate-e-one-digit-at-a-time — firefrorefiddle, Mar 17 '13 at 10:38
See e.g. "unbounded spigot algorithms" for example, Pi, http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf — Don Stewart, Mar 17 '13 at 12:03
Why don't you just take the digits from somewhere else (e.g. here: http://apod.nasa.gov/htmltest/gifcity/e.1mil ) and convert it to a binary representation at runtime? — Cubic, Mar 17 '13 at 12:08

score 7 · Accepted Answer · answered Mar 17 '13 at 12:46

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.

If I need to change it to output binary, do I just replace the 10 with 2? — zcaudate, Mar 18 '13 at 01:32

Daniel Wagner · Answer 2 · 2013-03-17T13:42:30.953

You might be interested in using CReal for this. For 100,000 binary digits, 30,200 decimal digits is enough:

Prelude> 100000 * logBase 10 2
30102.999566398114
Prelude> :m + Data.Number.CReal
Prelude> :set +s
Prelude Data.Number.CReal> last $ showCReal 1000 (exp 1)
'4'
(0.34 secs, 34061824 bytes)
Prelude Data.Number.CReal> last $ showCReal 2000 (exp 1)
'4'
(1.25 secs, 104478784 bytes)
Prelude Data.Number.CReal> last $ showCReal 4000 (exp 1)
'7'
(5.96 secs, 355775928 bytes)
Prelude Data.Number.CReal> last $ showCReal 8000 (exp 1)
'2'
(20.89 secs, 1298942504 bytes)

This pattern looks about quadratic to me, so computing the first 30,200 digits of exp 1 looks like it might reasonably finish in about five or six minutes here on my machine. A patch to output in binary directly (and therefore avoid converting to decimal and back) would likely be accepted.

edit: Projection satisfied, just under six minutes of compute time!

Prelude Data.Number.CReal> showCReal 30200 (exp 1)
"2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334...middle snipped due to StackOverflow message limit...39106913376148418348845963656215266103322394174671"
(349.44 secs, 17096829912 bytes)

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

2 Answers2