Is there such a method that computes 'e' to 'n' correct digits with less than 'n' iterations?

117 Views Asked by At

I have been looking into methods and formulae that yields approximations of 'e', one thing i have observed is that at least the ones i have tried tend to use by far more iterations than the number of correct digits they generate.

Is there no method that has a better convergence as well as less time needed to generate correct digits than them?.

1

There are 1 best solutions below

5
On BEST ANSWER

The power series expansion $$ \mathrm{e}^x = 1 + x + \frac{1}{2!} x^2 + \frac{1}{3!} x^3 + \cdots + \frac{1}{k!} x^k + \cdots $$ converges quite quickly. Set $x=1$ and you are just summing reciprocal factorials. The sum of the first $n$ terms, $s_n$, satisfies $$ s_n < \mathrm{e} < s_n + \frac{1}{n \cdot n!} $$ so is certainly gaining a digit of precision after $10$ terms, two digits each after $100$ terms, and so on. (Euler actually used this method to find $23$ decimal digits of his constant (that is, $23$ digits after the decimal). See L. Euler, Introduction à l'analyse infinitésimale (French translation by Labey), Barrois, ainé, Librairie, (original 1748, translation 1796), vol. 1, p. 89-90. In fact, page 89, just three lines above the marginal notation "(q)". As an amusing coincidence, this can be obtained after just $23$ terms.)

Binary splitting can be used to improve the running time of an implementation of this series method. See Xavier Gourdon and Pascal Sebah, Binary splitting method, 2001. This is usually overcomplex for "small" number of digits, but can be effective for thousands or millions (or more) of digits.