macrakis@harvard.ARPA (Stavros Macrakis) (12/13/84)
Calculating e from left to right really isn't that hard. I designed a
little program to do this in high school, about 13 years ago...
Let's consider a simpler problem first, namely calculating 1/x from
left to right. You can do this with the classic division algorithm:
Example:
___.142_...________
7 ) 1.000000000000000
.7
---
30
28
---
20
14
---
60 ...
At each stage, you need to keep only one intermediate result: the
remainder from the last partial division.
To calculate e, you want Sum(i,0,inf, 1/i!). Note that the i'th term
is just the i-1st over i. So to calculate this sum left to right, we
need to have, at the i'th stage, i partially complete divisions with
their i remainders:
Divisions Remainders
in process
1.00| 0
1.00| 0
0.50| 0
0.16| 2
0.04| 0
0.00| 4
----
Partial 2.70
sum
Of course, you don't output a digit until it is completely determined. This
may be a problem if there are partial sums of the form ...999999... (I don't
know of any upper bound on the length of 9-sequences in the expansion of e...).
The other practical matter is that it is probably most efficient to do all
your calculations in the largest number base 10^n that is convenient to do
arithmetic in; otherwise, you spend more calculation converting to base
10 than in calculating e!
The amount of storage needed is reasonable: about 3000 remainders for 10000
digits (3000! ~= 10^10000).