Machin's Merit
In 1938 Lehmer defined a measure of the computational merit
for arctangent expressions involving pi. He said the amount of
computational labor required to evaluate pi using the formula
pi N
--- = SUM c_k arctan(q_k)
4 k=1
(assuming the arctangent is evaluated using its Taylor's series
expansion) was proportional to
N 1
SUM ------------
k=1 log_10(1/q_k)
The most famous of these arctangent formulas, and one of the best,
is Machin's
pi
--- = 4 arctan(1/5) - arctan(1/239)
4
which has a "measure" of 1/log_10(5) + 1/log_10(239) = 1.8511.
In 1988 Castellanos published an extensive survey article on the
methods of computing pi, and he listed the "measures" of a large
number of arctangent formulas, including those found by Euler,
Gauss, and many others. Of all those listed (over two dozen), the
one with the best (i.e., smallest) "measure" is one attributed to
Klingenstierna:
pi / 3583 \
--- = 8 atan(1/10) - atan(1/100)- atan(1/515) - atan(-----------)
4 \371498882/
This has a measure of 1.0681. However, it's not hard to find
formulas with better Lehmer measures. For example,
pi / 1744507482180328366854565127 \
---- = 22 arctan(1/28) + arctan( -------------------------------- )
4 \98646395734210062276153190241239/
The argument of the right-hand arctangent is about 1/56546 so this
formula has a Lehmer measure of 0.9014. Needless to say this type
of formula is no longer used for calculating pi, having been
superceeded by far more efficient methods. Still, it raises the
question of whether there is a lower bound on possible Lehmer
measures for formulas of this type.
I think the answer to the above question is no, there is no lower
bound on the Lehmer measure, except zero. We have the identity
pi / 1 - tan(u) \
--- = u + arctan( ----------- )
4 \ 1 + tan(u) /
Setting u = N arctan(1/M) where N/M is a convergent of the
continued fraction for pi/4 ensures that (1-tan(u))/(1+tan(u))
is very small, much smaller than 1/M, so the Lehmer measure is
less than 2/log_10(M). Since we can make M as large as we
like, the measure can be made arbitrarily close to zero.
For example, a good rational approximation of pi/4 is 355/452,
so we can create the Machin formula
pi / 1 \ / 1 - tan(u)\
---- = 355 arctan( --- ) + arctan( ----------- )
4 \452/ \ 1 + tan(u)/
where u = 355 arctan(1/452). The argument of the rght-hand arctan
is a very small rational number, roughly 1/823723, so the Lehmer
measure for this formula is 0.5456.
This suggests a way of turning these formulas into a progressively
more rapidly convergent algorithm. Suppose we are given the first k
decimal digits of pi/4. We can use them to immediately compute 2k
digits. To illustrate, take just the first digit of pi/4, which is
0.7. Thus we can set N=7 and M=10 and compute several more digits
using the formula
pi / 1 \ / 1 - T \
---- = 7 arctan( --- ) + arctan( ------- )
4 \ 10/ \ 1 + T /
where T = tan(7a) and tan(a)= 1/10. This formula is exact, and
will give as many digits as we want, provided we evaluate enough
terms of the arctan series. However, to just double the number of
digits we only need to use the first two terms of the arctan
series, i.e., arctan(x) = x - (x^3)/3. The only challenging part
is to compute T = tan(Na), but this can be done in O(log(N)) steps
by using a binary exponentiation scheme with the equation
tan(x) + tan(y)
tan(x+y) = ----------------
1 - tan(x)tan(y)
Knowing tan(a)=1/10 we can quickly compute tan(7a). Then using
just the first two terms of the arctan series we compute
pi
---- ~= 0.78538...
4
which corresponds to a value of pi = 3.141532... This has actually
more than doubled our significant digits. (If we used the first
THREE terms of the arctan series this would give pi=3.141593...)
We only need to double at each step to give an exponentially
convergent algorithm, but we could easily make the algorithm
triple or quadruple or increase the number of digits by any
factor we want at each stage, simply by including a few more
terms of the arctan series.
Anyway, taking just the first two digits of pi/4 ~ 0.78 we repeat
the process, using the rational approximation 78/100. So now we
have the formula
pi / 1 \ / 1 - T \
---- = 78 arctan( ---- ) + arctan( ------- )
4 \ 100/ \ 1 + T /
where T = tan(78a) and tan(a)= 1/100. Again, this formula is exact,
be we only need the first two terms of the arctan series to double
the number of digits. Actually the first two terms give
pi/4 ~ 0.78539816 pi ~ 3.1415926 47
The basic algorithm actually tends to triple the number of digits,
because the arctan is of the form (1/10^k) - (1/3)(1/10^k)^3. If
the next term is included the above formula gives
pi/4 ~ 0.78539816339... pi ~ 3.1415926535902...
This shows how easy it is to more than triple the number of
correct digits at each stage. Anyway, sticking to our doubling
approach we have the new rational approximation pi/4 ~ 7853/10000,
so the next stage is to evaluate
pi / 1 \ / 1 - T \
---- = 7853 arctan( ------ ) + arctan( ------- )
4 \ 10000/ \ 1 + T /
where T = tan(7853a) and tan(a)= 1/10000. It may seem daunting
to evaluate tan(7853a) but using the binary exponentiation scheme
it only takes roughly log_2(7853) = 12 steps. This formula will
yield no less than 8 digits, the next no less than 16, and so on,
doubling at each stage. (Obviously this assumes the calculations
are being carried out to the required precision.)
Unfortunately, since the evaluation of tan(Na) takes about log(N)
operations, and since log(N) is proportional to the number of
digits of N, it's clear that the computational labor involved
in this method is roughly linear with the number of digits, so
this isn't as powerful as truly exponential methods such as
arithmetic-geometric mean algorithms.
Incidentally, the arctan series also leads directly to another of
the more common "low tech" methods of computing pi. Beginning with
the fact that tan(pi/4) = 1, we can take the arctan of both sides,
using the first two terms of the expansion, and multiply by 4 to
give
/ 1^3 \
pi = 4 arctan(1) ~ 4 ( 1 - --- ) = 8/3
\ 3 /
which gives an estimate of pi ~ 2.666. This obviously isn't very
good, but suppose we re-write the basic equation tan(pi/4)=1 in
the form
tan( pi/8 + pi/8 ) = tan(pi/4) = 1
By the addition formula for the tangent function we have
tan(pi/8) + tan(pi/8)
--------------------- = tan(pi/4)
1 - tan(pi/8)^2
We can solve this equation for tan(pi/8) to give
________________
-1 + / 1 + tan(pi/4)^2 _
tan(pi/8) = ---------------------- = /2 - 1
tan(pi/4)
This equation is exact, but it's more convenient for computation
because sqrt(2)-1 is only 0.414..., so the first two terms of the
arctangent give a more accurate result than with an argument of 1
as in the previous case. So, taking the arctan of both sides and
multiplying by 8 gives
_ _ _
_ | _ (/2 - 1)^3 |
pi = 8 arctan(/2 - 1) ~ 8 |(/2 - 1) - ---------- |
|_ 3 _|
This equals about 3.124... Needless to say, we can iterate this
operation. For example, we have
________________
-1 + / 1 + tan(pi/8)^2
tan(pi/16) = ----------------------
tan(pi/8)
In general, if we set t[0] = 1 and recursively compute subsequent
values of t[k] using the formula
_____________
-1 + / 1 + t[k-1]^2
t[k] = -------------------
t[k-1]
then we have a sequence of geometrically decreasing values of t[k],
and at any stage we can compute
/ t[k]^3 \
pi = 2^(k+2) arctan(t[k]) ~ 2^(k+2) ( t[k] - ------ )
\ 3 /
Going just to t[4] gives pi ~ 3.141592(4). Notice that each
successive value of t[k], expressed in binary, is just a closer
approximation of PI shifted one bit further to the right on each
step.
At each step this process essentially computs the tangent of the
arc of half the previous arc. Since tan(x) -> x as x approaches
zero, we can take PI ~ N tan(PI/N) as N goes to infinity. This
is the same basic approach that Archimedes took, computing the
perimeters of a sequence of regular polygons, doubling the number
of sides on each step. However, we started with a square, whereas
Archimedes actually started with a hexagon, using the fact that
tan(PI/6) = 1/sqrt(3), which is why he needed to know the value
of sqrt(3) for his computation of bounds on PI. Also, Archimedes
chose to work with a geometrically increasing (rather than
decreasing) sequence, so he performed his calculations in terms
of the reciprocals of the tangents. For more on this, see
From Euclid to Gregory.
For more on tangent formulas, see Tangents, Exponentials, and PI.
Return to MathPages Main Menu
Сайт управляется системой
uCoz