         Путь: Математика » Быстрые вычисления » Число е - мощные методы
Вычисление с большой точностью числа е  Если Вы найдете статью полезной и интересной - не сочтите за труд, переведите материал или хотя бы часть его и отправьте на адрес algolist@manual.ru. Задать вопросы или просто написать письмо можно также на странице контактов.

Статья любезно предоставлена:
© Xavier Gordon, numbers.computation.free.fr

The constant e

e = 2.71828182845904523536028747135266249775724709369996ј

" eip+1 = 0 , all analysis lies here"

Felix Klein (1849-1925).

1  Introduction  #### A function equal to it's own derivative

Let a be a real positive number, the exponential function ax (base a) is a differentiable function, that is the following limit exists

 (ax)ў = lim h® 0 жз и ax+h-axh цч ш = lim h® 0 жз и ah-1h цч ш ax = Cax.
A very important case is given when the derivative of the exponential function is equal to itself, which implies
 C = 1 = lim h® 0 жз и ah-1h цч ш ,
and can be written as
 a = lim h® 0 ( 1+h) 1/h.

This limit exists and it was denoted by the letter e by Euler, first in a letter to Goldbach in 1731, later in 1736 in his work. The origin of this choice is maybe due to the first letter of the word exponential. Hence the constant e is defined by the monotone increasing sequence

 e = lim n® Ґ en = lim n® Ґ жз и 1+ 1n цч ш n ,
but the convergence is very slow
 e1
 =
 2,
 e10
 =
 2.(59374246010...),
 e100
 =
 2.7(0481382942...),
 e1000
 =
 2.71(692393223...),
 e10000
 =
 2.718(14592682...),...
A quicker convergence is easily obtained by (see , , )
 e = lim n® Ґ жз и 2n+12n-1 цч ш n .
It's interesting to note that the constant e holds a key position in the simplest first order differential equation
 yў = y,
while p occurs in a similar second order differential equation.

Links between the previous definition and the law of compound interest in financial calculations are given in .

#### A famous sequence

Using the Newton's binomial theorem

 (1+x)n = 1+nx+ n(n-1)2 x2+...+xn,
for x = 1/n and after some manipulations gives the famous relation
 e
 =
 1+ 11 + 11×2 + 11×2×3 + 11×2×3×4 +ј
(1)
 =
 lim n® Ґ sn = lim n® Ґ жз и n е k = 0 1k! цч ш ,
(2)
given by Euler in 1748 . This relation is very efficient to compute e because the factorial of a number grows very quickly and it's easy to show that
 sn < e < sn+ 1n.n! .
Euler used this relation to find 23 digits of e.

The constant e is also known as the natural base of logarithm, that is

 log(e) = ух e 1 dxx = 1,
and is equal to the value of the exponential function at 1 :
 e = exp(1).

The number e is irrational (Euler 1744) and transcendental (Hermite 1873, ).

2  Continued fraction  In 1737 and 1748 , Euler published three important developments related to the constant e. It is more convenient to use the following notation:

x = a0+ 1
 a1+ 1a2+...
= [a0;a1,a2,a3,...]

The first development is

 e
 =
 [2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,...]
 e
 =
 жз и 2,3, 83 , 114 , 197 , 8732 , 10639 , 19371 , 1264465 , 1457536 , 27211001 ,ј цч ш

the second one

 Цe = [1;1,1,1,5,1,1,9,1,1,13,1,1,17,...]

and the last one is

 e-12
 =
 [0;1,6,10,14,18,22,26,30,34,38,42,...]
 e
 =
 жз и 0,3, 197 , 19371 , 27211001 , 4917118089 , 1084483398959 ,ј цч ш

Notice that, unlike p, those developments are dramatically regular.

### 2.1  An algorithm using continued fraction

Let pk/qk be the convergent of order k of a simple continued fraction, and let x = [a0;a1,a2,...,ak], we have the following recurrence relations

 pk
 =
 akpk-1+pk-2
 qk
 =
 akqk-1+qk-2

with initial conditions

 p-1
 =
 1,p0 = a0
 q-1
 =
 0,q0 = 1.
If we use the continued fraction for (e-1)/2, then ak = 4(k-1)+2 for k > 1 and it's easy to build an algorithm to compute a fast converging sequence to e. With k = 1500, e is given to 104 decimal places, with k = 12000, e is given to 105digits.

3  Using Padé approximant  If we consider the series expansion

 s(t) = Ґ е k = 0 sktk,sk О R

We are looking for a rational approximation of this sequence with numerator of degree m and denominator of degree n such as:

s(t)- ж
з
з
з
з
и
 m е k = 0 mktk

 n е k = 0 nktk
ц
ч
ч
ч
ч
ш
= O(tm+n+1),       t® 0

When such an approximation exists, it's called a Padé approximant of degree (m,n) of the series s. There are many properties associated with those approximants, they are used to compute series with bad convergence properties. Here we will just give the Padé approximant of the et function:

 m е k = 0 (m+n-k)!m!(m+n)!k!(m-k)! tk

 n е k = 0 (m+n-k)!n!(m+n)!k!(n-k)! (-t)k

For example here are some approximant of increasing degree for et:

 2+t2-t
 12+6t+t212-6t+t2
 120+60t+12t2+t3120-60t+12t2-t3
 ...

From this we may deduce that for small values of t, e = (et)1/twill be well approximated by

 жз и 2+t2-t цч ш 1/t
 жз и 12+6t+t212-6t+t2 цч ш 1/t
 жз и 120+60t+12t2+t3120-60t+12t2-t3 цч ш 1/t
 ...

The error being respectively O(t2),O(t4),O(t6),... The famous formula (1+t)1/t converges with an error O(t). As an example of the efficiency of the other formulas, the last formula for different values of t gives

 t = 1,
 e » 2.718(3098591549295...)
 t = 1/2,
 e » 2.71828(22539303576...)
 t = 1/4,
 e » 2.7182818(350588212...)
 t = 1/32,
 e » 2.7182818284590(703...)

4  Infinite products  There are several formulae to compute e as infinite products, one of them was given in 1873 by Catalan:

 e = 21 жз и 43 цч ш 1/2 жз и 6·85·7 цч ш 1/4 жз и 10·12·14·169·11·13·15 цч ш 1/8 ј,

and another similar relation is :

 e = 2 жз и 21 цч ш 1/2 жз и 2·43·3 цч ш 1/4 жз и 4·6·6·85·5·7·7 цч ш 1/8 ј

Like Wallis formula for p, the convergence is extremely slow.

Another product may be easily deduced from formula (1); let sn be the partial sum of this sequence

 sn = 1+ 11! +...+ 1n!
then
 sn+1 = sn+ 1(n+1)! = sn жз и 1+ 1(n+1)!sn цч ш = sn жз и 1+ 1un+1 цч ш .
Clearly un+1 is an integer and
 un
 =
 n!sn-1
 un+1
 =
 (n+1)!sn = (n+1)n!(sn-1+ 1n! ) = (n+1)(n!sn-1+1)
therefore, if we define the sequence un as following
 u1
 =
 1
 un+1
 =
 (n+1)(un+1)
we find
 e = Ґ Х n = 1 жз и un+1un цч ш = 2.( 54 )( 1615 )( 6564 )( 326325 )...

The rate of convergence is exactly the same as (1).

5  e and permutations  The number e occurs in the derangements of n objects. For example consider the set of 3 different objects S3 = (1,2,3), all the permutations of this set are

 (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)

and it is well known that the number of permutations of Sn is n! (in our example 6). But among some permutations how many don't have a fix point ? In the example the answer is 2, that is

 (2,3,1),(3,1,2)

but the general answer for a set of n objects is given by the following theorem.

Theorem 1 (Euler) Let dnbe the number of derangements of n different objects (dnis sometime called subfactorial), we have

 dn = n! жз и 1- 11! + 12! - 13! +...+ (-1)nn! цч ш .

Proof : Left as exercise. Hint: Show the recursion dn = (n-1)(dn-1+dn-2).·

Hence the ratio of the number of derangements to the number of permutations is

 dnn! = жз и 1- 11! + 12! - 13! +...+ (-1)nn! цч ш ,

this ratio is such as

 lim n® Ґ жз и dnn! цч ш = 1e = 0.3678794411714423215955237...

and for example

 d33!
 =
 23! = 0.3333333333...
 d44!
 =
 94! = 0.375
 d55!
 =
 445! = 0.3666666666...
 d66!
 =
 2656! = 0.3680555555...
 d77!
 =
 18547! = 0.3678571428...

6  Other limits  Before the description of efficient ways to compute e, let's consider An, the arithmetic mean of the quantities (1,2,3,...,n) and Gn, the geometric mean of the same quantities, that is

 An
 =
 1+2+3+...+nn = n(n+1)2n ,
 log(Gn)
 =
 log(1)+log(2)+...+log(n)n

or

 Gn = ( 1.2.3...n) 1/n = (n!)1/n,

then thanks to Stirling's formula, when n becomes large :

 AnGn = n+12(n!)1/n ~ n+12(nne-n(2pn)1/2) 1/n = e2 n+1n(2pn)1/(2n)

therefore

 lim n® Ґ AnGn = e2 .

A more general result was given in  and another similar result involving the geometric mean of the prime numbers was given in :

 lim n® Ґ жи Х pi Ј n pi цш 1/n = e

where the pi is the sequence of primes (2,3,5,7,11,13,...). The rate of converge is very slow and for example with n = 106, it gives 2.7141645...

7  A tiny program to compute e  This is a tiny C program from Xavier Gourdon to compute 9000 decimal digits of e on your computer. A program of the same kind exists for p.

```main(){int N=9009,n=N,a,x;while(--n)a[n]=1+1/n;
for(;N>9;printf("%d",x))
for(n=N--;--n;a[n]=x%n,x=10*a[n-1]+x/n);}
```

This program has 117 characters (try to do better !). It can be changed to compute more digits (change the value 9009 to more) and to be faster (change the constant 10 to another power of 10 and the printf command). A not so obvious question is to find the algorithm used.

8  Records of computation  Number of digits When Who Notes 23 1748 L. Euler The exponential series e = 1+1/1!+1/2!+... was used . 137 1853 W. Shanks See . 205 1871 W. Shanks 346 1884 Boorman See . 2010 1949 John von Neumann John von Neumann and his team  used the ENIAC. The result confirmed a previous computation to 808 digits published in 1946. 100,265 1961 D. Shanks and J.W. Wrench, Jr. Euler's formula was used on a IBM 7090. The computation took 2.5 hours . (See Math. Comp. 23, 679-680 (1969)) 10,000,000 1994 R. Nemiroff and J. Bonnell 18,199,978 1997, May Patrick Demichel 20,000,000 1997, Aug Birger Seifert The computation took 182.5 hours on a Pentium at 133 Mhz 50,000,817 1997, Sep Patrick Demichel The computation took 714 hours of a HP 9000/778 (160Mhz). 200,000,579 1999 S. Wedeniwski The method was based on binary splitting. 869,894,101 1999, Oct S. Wedeniwski The method was based on a continued fraction expansion of e. 1,250,000,000 1999, Nov X. Gourdon The formula used was the exponential series e = е1/n!, the verification was made with e = 1/(е(-1)n/n!). A binary splitting technique was used. The computation took  40 hours on a PentiumII 350 with 320 Mo. 4 Go of disk space was used during the process. (Note : a previous 1.7 billion digits computation by Patrick Demichel was made before, but no verification was performed. It appears that its first 1.25 billion digits are OK). 2,147,483,648 2000, Jul 10 S. Kondo and X. Gourdon The computation was launched by Shigeru Kondo with the program PiFast33 written by X. Gourdon. The same technique as in the previous record was used. The computation took 21 hours on a PentiumIII 933 with 512 Mo. 8 Go of disk space were used during the process. 3,221,225,472 2000, Jul 16 C. Martin and X. Gourdon Colin Martin used the same PiFast33 program on an Athlon 650 with just 128 Mo. of physical memory and 17.2 GB of disk space. The initial calculation took just over 77 hours and completed on July 13th and the verification took 80 hours. 6,442,450,944 2000, Aug 02 S. Kondo and X. Gourdon Shigeru Kondo used PiFast33 again. The computation took 70 hours on a PentiumIII 800 with 1024 Mo. 24 Go of disk space were necessary. The verification took 71 hours on the same machine.

References  L. Euler, Introduction à l'analyse infinitésimale (french traduction by Labey), Barrois, ainé, Librairie, (original 1748, traduction 1796), vol. 1, p. 89-90


W. Shanks, Contributions to Mathematics Comprising Chiefly the Rectification of the Circle to 607 Places of Decimals, G. Bell, London, (1853), p. vii.


C. Hermite, Sur la fonction exponentielle, C. R. Académie des Sciences, (1873), vol. 77, p. 18-24, 74-79, 226-233, 285-293


Boorman, (On the value of e), The Mathematical Magazine, (1884), vol. 1, p. 204


L W. Richardson, The deferred Approach to the Limit, Philosophical Transactions of the Royal Society of London, (1927), serie A, vol. 226


G. W. Reitwiesner , An ENIAC Determination of p and e to more than 2000 Decimal Places, Mathematical Tables and other Aids to Computation, (1950), vol. 4, p. 11-15


K. Knopp, Theory and application of infinite series, Blackie & Son, London, (1951)


D. Shanks and J.W. Wrench, Jr., Calculation of p to 100,000 Decimals, Math. Comput., (1962), vol. 16, p. 76-79


F. Le Lionnais, Les nombres remarquables, Paris, Hermann, (1983), p. 47


J.M. Borwein and P.B. Borwein, Pi and the AGM - A study in Analytic Number Theory and Computational Complexity, A Wiley-Interscience Publication, New York, (1987)


E. Maor, e: The Story of a Number, Princeton University Press, (1994)


Brothers, Harlan J. and J.A. Knox, New closed-form approximations to the logarithmic constant e, Math. Intelligencer, (1998)


J. A. Knox and Harlan J. Brothers, Novel series-based approximations to e, College Math. J., (1998)


E. W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC Press, (1999), p. 503-504