Machin's Merit

 

In 1938 Lehmer defined a measure of the computational merit for arctangent expressions involving π.  He said the amount of computational labor required to evaluate π using the formula

 

 

(assuming the arctangent is evaluated using its Taylor's series expansion) was proportional to

 

 

The most famous of these arctangent formulas, and one of the best, is Machin's

 

 

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:

 

 

This has a measure of 1.0681.  However, it's not hard to find formulas with better Lehmer measures, although it’s debatable whether these are actually better for computational purposes.  For example,

 

 

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 π, having been superceded 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.

 

The answer to the above question is no, there is no lower bound on the Lehmer measure, except zero.  We have the identity

 

 

Setting  u = N arctan(1/M)  where N/M is a convergent of the continued fraction for π/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/log10(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 π/4 is 355/452, so we can create the Machin formula

 

 

where u = 355 arctan(1/452).  The argument of the right-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 π/4.  We can use them to immediately compute 2k digits.  To illustrate, take just the first digit of π/4, which is 0.7.  Thus we can set N = 7 and M = 10 and compute several more digits using the formula

 

 

where T = tan(7α) with tan(α) = 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 − (x3)/3.  The only challenging part is to compute T = tan(Nα), but this can be done in O(log(N)) steps by using a binary exponentiation scheme with the equation

 

 

Knowing tan(α) = 1/10 we can quickly compute tan(7α).  Then using just the first two terms of the arctan series we compute

 

 

which corresponds to a value of π = 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 π = 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.

 

Taking just the first two digits of π/4 ~ 0.78 we repeat the process, using the rational approximation 78/100. So now we have the formula

 

 

where T = tan(78α) with tan(α) = 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

 

 

The basic algorithm actually tends to triple the number of digits, because the arctan is of the form (1/10k) − (1/3)(1/10k)3.  If the next term is included the above formula gives

 

 

This shows how easy it is to more than triple the number of correct digits at each stage.  Sticking to our doubling approach we have the new rational approximation π/4 ~ 7853/10000, so the next stage is to evaluate

 

 

where T = tan(7853α) with tan(α) = 1/10000.  It may seem daunting to evaluate tan(7853α) but using the binary exponentiation scheme it only takes roughly log2(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(Nα) 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 primitive methods of computing π. Beginning with the fact that tan(π/4) = 1, we can take the arctan of both sides, using the first two terms of the expansion, and multiply by 4 to give

 

 

which gives an estimate of π ~ 2.666. This obviously isn't very good, but suppose we re-write the basic equation tan(π/4) = 1 in the form

 

 

By the addition formula for the tangent function we have

 

 

We can solve this equation for tan(π/8) to give

 

 

This equation is exact, but it's more convenient for computation because  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

 

 

This equals about 3.124...  Needless to say, we can iterate this operation.  For example, we have

 

 

In general, if we set t0 = 1  and recursively compute subsequent values of tn using the formula

 

 

then we have a sequence of geometrically decreasing values of tk, and at any stage we can compute

 

 

Going just to t4 gives π ~ 3.141592(4).  Notice that each successive value of tk, expressed in binary, is just a closer approximation of π shifted one bit further to the right on each step.

 

At each step this process essentially computes the tangent of the arc of half the previous arc.  Since tan(x) → x as x approaches zero, we can take π ~ N tan(π/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(π/6) = 1/√3, which is why he needed to know the value of the square root of 3 for his computation of bounds on π.  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 the note From Euclid to Gregory. For more on tangent formulas in general, see Tangents, Exponentials, and π.

 

Return to MathPages Main Menu