series

[John Hughes]

	hello, i just want to ask a simple question: does somebody have or know =
	where to find a haskell program that calculates the number e, that is =
	the list of infinite digits? Because i think it may be possible to do =
	it, but i haven=B4t find the way to do it.
	what i am looking for is something like the ertostenes sifts, that =
	prints every prime number until it run out of memory...
	thank you,
	                Luis

It's a nice problem, which I encountered many years ago as one of the first
examples I saw of lazy evaluation! The point is, of course, to produce the
infinite stream of digits of e itself, not some approximation to it, as a
couple of solutions posted earlier do. I'm attaching my solution (a literate
Haskell script) which produces about 250 digits before hugs runs out of memory.

John Hughes

-----------------------------------------------------------------------------


Here's a way to compute all the digits of e. We use the series

   e = 2  +  1  +  1  +  1  +  ...
             --    --    --  
             2!    3!    4!

which we can think of as representing e as 2.11111... in a strange number
system with a varying base. In this number system, the fraction 0.abcd...
represents

             a  +  b  +  c  +  d  +  ...
	     --    --    --    --
	     2!    3!    4!    5!

To convert such a fraction to decimal, we multiply by 10, take the integer
part for the next digit, and continue with the fractional part. Multiplying
by 10 is easy: we just multiply each "digit" by 10, and then propagate carries.

The hard part is knowing how far carries might propagate: since we carry
leftwards in an infinite expansion, we must be careful to avoid needing to
inspect the entire fraction in order to decide on the first carry. But each
fraction we work with is less than one, so after multiplying by 10, it is less
than 10. The "carry out" from each digit can be at most 9, therefore. So if a
carry of 9 from the next digit would not affect the carry out from the current
one, then that carry out can be emitted immediately. Since the base soon
becomes much larger than 10, then this is likely to happen quickly. No doubt
there are much better ways than this of solving the problem, but this one
works.

> carryPropagate base (d:ds)
>   | carryguess == (d+9) `div` base 
>       = carryguess : (remainder+nextcarry) : fraction
>   | otherwise
>       = (dCorrected `div` base) : (dCorrected `mod` base) : fraction
>   where carryguess = d `div` base
>         remainder = d `mod` base
> 	  nextcarry:fraction = carryPropagate (base+1) ds
>         dCorrected = d + nextcarry

> e = ("2."++) $ 
>     concat $
>     map (show.head) $
>     iterate (carryPropagate 2 . map (10*) . tail) $
>     2:[1,1..]