0709dfe2ef8ac704944af1267822580720efe754
[nofib.git] / imaginary / digits-of-e2 / Main.lhs
1 Compute digits of e
2 Due to John Hughes, Aug 2001
3
4 > module Main where
5 > import System.Environment
6
7 Here's a way to compute all the digits of e. We use the series
8
9    e = 2  +  1  +  1  +  1  +  ...
10              --    --    --
11              2!    3!    4!
12
13 which we can think of as representing e as 2.11111... in a strange
14 number system with a varying base. In this number system, the fraction
15 0.abcd... represents
16
17              a  +  b  +  c  +  d  +  ...
18              --    --    --    --
19              2!    3!    4!    5!
20
21 To convert such a fraction to decimal, we multiply by 10, take the
22 integer part for the next digit, and continue with the fractional
23 part. Multiplying by 10 is easy: we just multiply each "digit" by 10,
24 and then propagate carries.
25
26 The hard part is knowing how far carries might propagate: since we
27 carry leftwards in an infinite expansion, we must be careful to avoid
28 needing to inspect the entire fraction in order to decide on the first
29 carry. But each fraction we work with is less than one, so after
30 multiplying by 10, it is less than 10. The "carry out" from each digit
31 can be at most 9, therefore. So if a carry of 9 from the next digit
32 would not affect the carry out from the current one, then that carry
33 out can be emitted immediately. Since the base soon becomes much
34 larger than 10, then this is likely to happen quickly. No doubt there
35 are much better ways than this of solving the problem, but this one
36 works.
37
38 > carryPropagate base (d:ds)
39 >   | carryguess == (d+9) `div` base
40 >       = carryguess : (remainder+nextcarry) : fraction
41 >   | otherwise
42 >       = (dCorrected `div` base) : (dCorrected `mod` base) : fraction
43 >   where carryguess = d `div` base
44 >         remainder = d `mod` base
45 >         nextcarry:fraction = carryPropagate (base+1) ds
46 >         dCorrected = d + nextcarry
47
48 > e :: String
49 > e = ("2."++) $
50 >     tail . concat $
51 >     map (show.head) $
52 >     iterate (carryPropagate 2 . map (10*) . tail) $
53 >     2:[1,1..]
54
55 > main = do
56 >       [digits] <- getArgs
57 >       print (take (read digits) e)