Если Вы найдете статью полезной и интересной  не сочтите за труд,
переведите материал или хотя бы часть его и отправьте на адрес
algolist@manual.ru.
Задать вопросы или просто написать письмо можно
также на странице контактов.
Let a be a real positive number, the exponential function a^{x}
(base a) is a differentiable function, that is the following limit exists
(a^{x})^{ў} =
lim
h® 0
ж з
и
a^{x+h}a^{x}h
ц ч
ш
=
lim
h® 0
ж з
и
a^{h}1h
ц ч
ш
a^{x} = Ca^{x}.
A very important case is given when the derivative of the exponential
function is equal to itself, which implies
C = 1 =
lim
h® 0
ж з
и
a^{h}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® Ґ
e_{n} =
lim
n® Ґ
ж з
и
1+
1n
ц ч
ш
n
,
but the convergence is very slow
e_{1}
=
2,
e_{10}
=
2.(59374246010...),
e_{100}
=
2.7(0481382942...),
e_{1000}
=
2.71(692393223...),
e_{10000}
=
2.718(14592682...),...
A quicker convergence is easily obtained by (see [5],
[12], [13])
e =
lim
n® Ґ
ж з
и
2n+12n1
ц ч
ш
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 [11].
A famous sequence
Using the Newton's binomial theorem
(1+x)^{n} = 1+nx+
n(n1)2
x^{2}+...+x^{n},
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® Ґ
s_{n} =
lim
n® Ґ
ж з
и
n е
k = 0
1k!
ц ч
ш
,
(2)
given by Euler in 1748 [1]. This relation is very efficient to
compute e because the factorial of a number grows very quickly and it's
easy to show that
s_{n} < e < s_{n}+
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, [3]).
Let p_{k}/q_{k} be the convergent of order k of a simple continued
fraction, and let x = [a_{0};a_{1},a_{2},...,a_{k}], we have the following
recurrence relations
p_{k}
=
a_{k}p_{k1}+p_{k2}
q_{k}
=
a_{k}q_{k1}+q_{k2}
with initial conditions
p_{1}
=
1,p_{0} = a_{0}
q_{1}
=
0,q_{0} = 1.
If we use the continued fraction for (e1)/2, then a_{k} = 4(k1)+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 10^{4} decimal places,
with k = 12000, e is given to 10^{5}digits.
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
m_{k}t^{k}
n е
k = 0
n_{k}t^{k}
ц ч ч
ч ч ш
= O(t^{m+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 e^{t} function:
m е
k = 0
(m+nk)!m!(m+n)!k!(mk)!
t^{k}
n е
k = 0
(m+nk)!n!(m+n)!k!(nk)!
(t)^{k}
For example here are some approximant of increasing degree for e^{t}:
2+t2t
12+6t+t^{2}126t+t^{2}
120+60t+12t^{2}+t^{3}12060t+12t^{2}t^{3}
...
From this we may deduce that for small values of t, e = (e^{t})^{1/t}will
be well approximated by
ж з
и
2+t2t
ц ч
ш
1/t
ж з
и
12+6t+t^{2}126t+t^{2}
ц ч
ш
1/t
ж з
и
120+60t+12t^{2}+t^{3}12060t+12t^{2}t^{3}
ц ч
ш
1/t
...
The error being respectively O(t^{2}),O(t^{4}),O(t^{6}),... 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
The number e occurs in the derangements of n objects. For
example consider the set of 3 different objects S_{3} = (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 S_{n} 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 d_{n}be the number of derangements of n different
objects (d_{n}is sometime called subfactorial), we have
d_{n} = n!
ж з
и
1
11!
+
12!

13!
+...+
(1)^{n}n!
ц ч
ш
.
Proof :
Left as exercise. Hint: Show the recursion d_{n} = (n1)(d_{n1}+d_{n2}).·
Hence the ratio of the number of derangements to the number of permutations
is
Before the description of efficient ways to compute e, let's consider A_{n}, the arithmetic mean of the quantities (1,2,3,...,n) and G_{n}, the geometric mean of the same quantities, that is
A_{n}
=
1+2+3+...+nn
=
n(n+1)2n
,
log(G_{n})
=
log(1)+log(2)+...+log(n)n
or
G_{n} = ( 1.2.3...n) ^{1/n} = (n!)^{1/n},
then thanks to Stirling's formula, when n becomes large :
A_{n}G_{n}
=
n+12(n!)^{1/n}
~
n+12(n^{n}e^{n}(2pn)^{1/2}) ^{1/n}
=
e2
n+1n(2pn)^{1/(2n)}
therefore
lim
n® Ґ
A_{n}G_{n}
=
e2
.
A more general result was given in [7] and another similar result
involving the geometric mean of the prime numbers was given in
[9]:
lim
n® Ґ
ж и
Х
p_{i} Ј n
p_{i}
ц ш
1/n
= e
where the p_{i} is the sequence of primes (2,3,5,7,11,13,...). The rate
of converge is very slow and for example with n = 10^{6}, it gives 2.7141645...
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.
John von Neumann and his team [6]
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 [8]. (See Math.
Comp. 23, 679680 (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.
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. 1115
J.M. Borwein and P.B. Borwein, Pi and the AGM  A study
in Analytic Number Theory and Computational Complexity, A
WileyInterscience Publication, New York, (1987)