На правах рекламы
Для вас со скидками аксессуары для кухни по привлекательной цене.
Логарифм 2
Если Вы найдете статью полезной и интересной  не сочтите за труд,
переведите материал или хотя бы часть его и отправьте на адрес
algolist@manual.ru.
Задать вопросы или просто написать письмо можно
также на странице контактов.
The story of logarithms really began with the Scot John Napier (15501617)
in a work published in 1614. This treatise was in Latin and entitled ''Mirifici logarithmorum canonis descriptio'' [7]. This invention
received an extraordinary welcome and George Gibson wrote during Napier
Tercentenary Exhibition : ''... the invention of logarithms marks
an epoch in the history of science''.
Very soon tables of logarithms were published. One of the first was due to
the English mathematician Henry Briggs (15611631) who, in 1624, published
his work in ''Arithmetica logarithmica'' [4]; the tables
were to an accuracy of fourteen digits and containing the common logarithm
of integers up to 20000 and from 90000 up to 101000. The remaining gap was
completed [12] by the Dutchman Adrian Vlacq (16001667) in 1628.
The natural logarithm of a number x is now defined by :
Definition 1
Let x > 0
log(x)=
у х
x
1
dt
t
=
у х
x1
0
dt
1+t
It may be interpreted as the area under the hyperbola y=1/t with t going
from1 to x. (this geometric interpretation was showed by the Jesuit
Grégoire de SaintVincent (15841667) in 1647).
Therefore, log(2) will be defined by
log(2)=
у х
2
1
dt
t
=
у х
1
0
dt
1+t
=
у х
1/2
0
dt
1t
.
Theorem 2
log(2) is an irrational and transcendental number.
From the integral representation of log(2) we may deduce some formulae.
The first one is deduced form the rectangular approximation of the
integral (here h=(ba)/n)
у х
b
a
f(t) dt=h
n е
k=1
f(a+kh)+O(h),
which, applied to f(t)=1/(1+t) on [0,1] gives
log(2)=
lim
n® Ґ
ж и
1
n+1
+
1
n+2
+...+
1
2n
ц ш
.
This sequence is increasing. Here are the numerical values of some partial
sum for different value of n.
x_{10}
=
0.6(687...)
x_{100}
=
0.69(065...)
x_{1000}
=
0.69(289...)
It's a very slow convergence, but it can be improved if we use the trapezoidal rule
у х
b
a
f(t)dt=
h
2
ж и
f(a)+f(b)+2
n1 е
k=1
f(a+kh)
ц ш
+O(h^{2}),
yielding
log(2)=
lim
n® Ґ
ж и
3
4n
+
ж и
1
n+1
+
1
n+2
+ј+
1
2n1
ц ш
ц ш
and some iterates are
x_{10}
=
0.693(771...)
x_{100}
=
0.6931(534...)
x_{1000}
=
0.693147(243...)
The rate of convergence has been improved but it remains logarithmic. We now
give a last improvement on the computation of the integral, known as the
Simpson's rule
у х
b
a
f(t)dt=
h
6
n е
k=0
ж и
f(a+kh)+f(a+(k1)h)+4f
ж и
a+(k
1
2
)h
ц ш
ц ш
+O(h^{4}),
giving
log(2)=
lim
n® Ґ
n е
k=0
ж и
1
n+k
+
1
n+k1
+
4
n+k1/2
ц ш
and the new iterates
x_{10}
=
0.693147(374...)
x_{100}
=
0.6931471805(794...)
x_{1000}
=
0.69314718055994(726...)
From those examples we can notice that such formulae may only be used to
compute a few digits of log(2), the rate of convergence is too slow to
find constants with high precision.
In 1668, Nicolas Mercator (16201687) published in his Logarithmotechnia [6] the well known series expansion for the
logarithmic function :
Theorem 3
(Mercator)
log(1+x)=x
x^{2}
2
+
x^{3}
3
...=
е
k і 1
(1)^{k1}x^{k}
k
. 1 < x Ј 1
The Mercator series is very similar to another series studied by James
Gregory (16381675) at the same time :
arctan(x)=x
x^{3}
3
+
x^{5}
5
ј
One of the first mathematician to use Mercator's series is Isaac Newton
(16431727) who made various computation of logarithms in the celebrated
''De Methodis Serierum et Fluxionum'' written in 1671 but only
published and translated from Latin to English in 1736, by John Colson. He
made several accurate computations for small values of x, like ±0.1,±0.2 and was then able to compute logarithms of larger numbers using
relations like log(2)=2log(1.2)log(0.9)log(0.8).
Applying the Mercator series for x=1 leads to the famous and very slowly
convergent sequence
log(2)=1
1
2
+
1
3

1
4
+
1
5
...
which first values, taking respectively 10, 100, 1000 and 10000 terms are :
x_{10}
=
0.6(456...)
x_{100}
=
0.6(881...)
x_{1000}
=
0.69(264...)
x_{10000}
=
0.693(097...).
A much better idea is to apply the series with x=1/2, this produces a
formula that was often used for numerical computation:
log(2)=
е
k і 1
1
k2^{k}
(1)
The rate of convergence is now geometric (p iterations are needed to
obtain one more digits).
x_{1}
=
0.(5)
x_{10}
=
0.693(064...)
x_{100}
=
0.6931471805599453094172321214581(688...)
Applying the formula up to k=1000 gives more than 300 digits for log(2). The number of iterations k needed to obtain d decimal digits is
given by (with N=2 in the previous formula)
1
10^{d}
=
1
kN^{k}
which gives for large values of k
k »
d
log_{10}(N)
If we use the trivial decomposition 2=(4/3)(3/2) and take the logarithm of
both side of the equality we find a new formula
log(2)=
е
k і 1
1
k
ж и
1
3^{k}
+
1
4^{k}
ц ш
The partial sum of this series up to k=1000 will give more than 470 digits.
From the relation log(2)=1/2log(11/4)+ arctanh(1/2), (see next
paragraph for the definition of arctanh) we deduce the relations
log(2)
=
е
k і 0
ж и
1
8k+8
+
1
4k+2
ц ш
1
4^{k}
,
log(2)
=
2
3
+
е
k і 1
ж и
1
2k
+
1
4k+1
+
1
8k+4
+
1
16k+12
ц ш
1
16^{k}
.
Those formulae can also be used to compute directly the nth binary
digit of log(2) without computing the previous ones.
Using Mercator series has improved a lot our ability to compute many digits
for log(2), but like for the number p it's possible to go further.
We recall the definition of the inverse hyperbolic tangent.
Definition 4
Let x < 1:
arctanh(x)=
1
2
log
ж и
1+x
1x
ц ш
=
е
k і 0
x^{2k+1}
2k+1
.
For x=1/3, this leads easily to the basic formula log(2)=2 arctanh(1/3) which is similar to the formula p = arctan(1). We
rewrite it as :
log(2)=
2
3
е
k і 0
1
(2k+1)9^{k}
Two iterates are then :
x_{1}
=
0.6(666...)
x_{10}
=
0.6931471805(498...).
Applying the formula up to k=1000 gives more than 950 digits for log(2). Is it possible to do better? There is a famous formula for p,this formula is known as Machin's formula and is given by the
celebrated relation :
p
4
=4arctan
ж и
1
5
ц ш
arctan
ж и
1
239
ц ш
The idea is to look for relations like this one for log(2). If we note (a_{1},a_{2},...,a_{n}) a set of rational numbers and (p_{1},p_{2},...,p_{n}) a set of increasing integers we are looking for
relations like
log(2)=
n е
i=1
a_{i} arctanh
ж и
1
p_{i}
ц ш
We also want the formula to be efficient. A good relation is a
compromise between a small number of terms (n must be small) and large
values for the p_{i}. According to Lehmer, we define the efficiency E by
Definition 5
(Lehmer's measure). Let p_{i} > 0 a set of n numbers, then :
E=
n е
i=1
1
log_{10}(p_{i}^{2})
.
For example the efficiency of log(2)=2 arctanh(1/3) (n=1,p_{1}=3) is 1.05. With the same definition the efficiency of Machin's formula is 0.926
(n=2,p_{1}=5,p_{2}=239), so it's a little bit more efficient than the
formula for log(2).
It's possible to show the following decomposition theorem :
Theorem 6
Let p > 1:
arctanh
ж и
1
p
ц ш
=
arctanh
ж и
1
2p1
ц ш
+ arctanh
ж и
1
2p+1
ц ш
arctanh
ж и
1
p
ц ш
=
2 arctanh
ж и
1
2p1
ц ш
 arctanh
ж и
1
2p^{2}1
ц ш
arctanh
ж и
1
p
ц ш
=
2 arctanh
ж и
1
2p+1
ц ш
+ arctanh
ж и
1
2p^{2}1
ц ш
arctanh
ж и
1
p
ц ш
=
2 arctanh
ж и
1
2p
ц ш
+ arctanh
ж и
1
4p^{3}3p
ц ш
Applying this theorem for p=3 gives relations with n=2 :
Corollary 7
log(2)
=
2 arctanh
ж и
1
5
ц ш
+2 arctanh
ж и
1
7
ц ш
Euler1748
(2)
log(2)
=
4 arctanh
ж и
1
5
ц ш
2 arctanh
ж и
1
17
ц ш
(3)
log(2)
=
4 arctanh
ж и
1
7
ц ш
+2 arctanh
ж и
1
17
ц ш
(4)
log(2)
=
4 arctanh
ж и
1
6
ц ш
+2 arctanh
ж и
1
99
ц ш
(5)
The efficiencies are respectively E=1.307,E=1.121,E=0.998 and E=0.893.
Using other decomposition formulas and computer calculation it's possible to
find many other relations of this nature (given in [8]). To
illustrate this, we select another formula with 3 terms and two others with
4 terms.
Theorem 8
(Sebah 1997). The constant log(2) may be obtained by one of the
following fast converging series :
18 arctanh
ж и
1
26
ц ш
2 arctanh
ж и
1
4801
ц ш
+8 arctanh
ж и
1
8749
ц ш
,
(6)
144 arctanh
ж и
1
251
ц ш
+54 arctanh
ж и
1
449
ц ш
38 arctanh
ж и
1
4801
ц ш
+62 arctanh
ж и
1
8749
ц ш
,
(7)
72 arctanh
ж и
1
127
ц ш
+54 arctanh
ж и
1
449
ц ш
+34 arctanh
ж и
1
4801
ц ш
10 arctanh
ж и
1
8749
ц ш
.
(8)
The efficiency are respectively (E=0.616,E=0.659,E=0.689). The two last
formulae were used to compute more than 10^{8} digits for log(2). One
was used for the computation and the other for the verification and , as you
can see, only the computation of 5 arctanh were necessary because of the
similitude of the 2 formulae. Thanks to relation (6), the
record was increased up to more than 5.10^{8} a few years later.
Note that it's also possible to perform separately the computation of each
term, making those relations parallelisable.
We give, for example, the first iterates of the second formula (the one with
251):
where a,b,c are real numbers. The series converges in z < 1. On the
circle z=1, the series converges when c > a+b. Those functions are
called hypergeometric functions [1]. Many usual
functions can be represented as hypergeometric functions with suitable
values for a,b,c.
Example 10
ln(1+x)
=
xF(1,1;2;x)
arctanh(x)
=
xF(
1
2
,1;
3
2
;x^{2})
arctan(x)
=
xF(
1
2
,1;
3
2
;x^{2})
1
1x
=
F(1,1;1;x)
In 1797, Johann Friederich Pfaff (17651825), a friend of Gauss, gave the
interesting relation
F(a,b;c;z)=(1z)^{b}F(ca,b;c;
z
z1
).
If we apply this identity to the arctanh function
arctanh(x)=xF(
1
2
,1;
3
2
;x^{2}),
we find
arctanh(x)=
x
(1x^{2})
F(1,1;
3
2
;
x^{2}
x^{2}1
),
giving a new sequence for this function
arctanh(x)=
x
(1x^{2})
ж и
1
2
3
ж и
x^{2}
1x^{2}
ц ш
+
2.4
3.5
ж и
x^{2}
1x^{2}
ц ш
2

2.4.6
3.5.7
ж и
x^{2}
1x^{2}
ц ш
3
+...
ц ш
and with log(2)=2 arctanh(1/3); after some easy manipulations comes the
series :
Corollary 11
log(2)=
3
4
ж и
1
1
12
+
1.2
12.20

1.2.3
12.20.28
+...
ц ш
.
Each new term of this series is multiplied by k/(8k+4) where k=1,2,...
The same kind of formula was given by Euler to compute p. One nice
application of this corollary is to make it feasible to write a tiny code to
compute log(2) just like it was done for p.
The rate of convergence of all the previous series were logarithmic or
geometric. It's possible to find for log(2) just as for p, a
sequence that will have quadratic convergence, based on the AGM
(ArithmeticGeometric Mean) (see [2]).
The most classical among the AGM based quadratic convergence algorithms for log(2) is the following. Starting from a_{0} and b_{0} > 0, we consider
the AGM iteration
a_{n+1}=
a_{n}+b_{n}
2
, b_{n+1}=
Ц
a_{n}b_{n}
,
and we use the notation
R(a_{0},b_{0})=
ж з
и
1
1
е
n і 0
2^{n1}(a_{n}^{2}b_{n}^{2})
ц ч
ш
.
Theorem 12
Let N і 3 and 1/2 Ј x Ј 1,
 log(x)R(1,10^{N})+R(1,10^{N}x) Ј
N
10^{2(N2)}
.
(11)
By choosing x=1/2, this algorithm gives about 2N decimal digits of log(2). The convergence is quadratic and should be stopped when 2^{n1}(a_{n}^{2}b_{n}^{2}) is less than 10^{2N}, which occurs for n » log_{2}(N).
Notice that this algorithm is not specific to the computation of log(2)
and can be used to evaluate log(x) for any real number x. Using FFT
multiplication, its complexity is O(nlog^{2}(n)) to obtain n digits of
x.
He used log(2)=2log(1.2)log(0.9)log(0.8) and Mercator's series for log.
25
1748
L. Euler
Relation (2) was used. Euler also
computed the natural logarithm of integers from to 3 to 10 with 25 digits
[5].
137
1853
W. Shanks
Shanks also computed log(3), log(5) and log(10) with 137 digits. His work was published with a p
calculation [9].
273
1878
Adams
Adams also computed log(3), log(5) and log(7) with the same precision.
330
1940
H. S. Uhler
Uhler also computed log(3), log(5), log(7) and log(17) with the same precision [11].
3 683
1962
D.W. Sweeney
The computation of log(2) was necessary
for a computation of Euler's constant up to 3566 digits in the same
article). The formula used for log2 was the expansion (1)
(see [10]).
2 015 926
1997
P. Demichel
The computation used a classical approach
on formula (2). It took 16 hours on a HP9000/871 at 160MHz.
5 039 926
1997
P. Demichel
The same technique was used and the
computation took 130 hours on the same computer.
10 079 926
1997
P. Demichel
Same technique, 400 hours on the same
computer.
29 243 200
1997 Dec
X. Gourdon
The AGM formulae (11) was
used (with FFT techniques). The computation was done on a SGI R10000
workstation and took 20 hours 58 minutes.
58 484 499
1997 Dec
X. Gourdon
Same AGM technique, 83 hours on the
same computer.
108 000 000
1998 Sep
X. Gourdon
The four term formula (7) was used together with a binary
splitting process. Formula (8) was used for the
verification. The computation took 47 hours on a PII 450 with 256 Mo.
200 001 000
2001 Sep
X. Gourdon & S. Kondo
Formulae (6)
and (5) were used. The computation took 8 hours on an Athlon 1300
with 2 Go.
240 000 000
2001 Sep
X. Gourdon & P. Sebah
Formulae (6)
and (10) were used. The computation took 14 hours on a PIV
1400 with 1024 Mo.
500 000 999
2001 Sep
X. Gourdon & S. Kondo
Formulae (6)
and (10) were used. The computation took 28 hours on a PIV
1400 with 1024 Mo.
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)