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