Machin-like formula

In mathematics, Machin-like formulae are a popular technique for computing to a large number of digits. They are generalizations of John Machin's formula from 1706:
which he used to compute to 100 decimal places.
Machin-like formulas have the form
where formula_2 and formula_3 are positive integers such that formula_4, formula_5 is a signed non-zero integer, and formula_6 is a positive integer.
These formulae are used in conjunction with the Taylor series expansion for arctangent:
Derivation.
The following equations were derived in Angle addition formula:
Algebraic manipulation of these equations yields the following:
if
All of the Machin-like formulae can be derived by repeated application of equation . As an example, we show the derivation of Machin's original formula:
An insightful way to visualize equation is to picture what happens when two complex numbers are multiplied together:
The angle associated with a complex number formula_29 is given by:
Thus, in equation , the angle associated with the product is:
Note that this is the same expression as occurs in equation . Thus equation can be interpreted as saying that the act of multiplying two complex numbers is equivalent to adding their associated angles (see multiplication of complex numbers).
The expression:
is the angle associated with:
Equation can be re-written as:
Here formula_35 is an arbitrary constant that accounts for the difference in magnitude between the vectors on the two sides of the equation. The magnitudes can be ignored, only the angles are significant.
Using complex numbers.
Other formulas may be generated using complex numbers. For example, the angle of a complex number formula_36 is given by formula_37 and, when one multiplies complex numbers, one adds their angles. If a=b then formula_37 is 45 degrees or formula_39 radians. This means that if the real part and complex part are equal then the arctangent will equal formula_39. Since the arctangent of one has a very slow convergence rate if we find two complex numbers that when multiplied will result in the same real and imaginary part we will have a Machin-like formula. An example is formula_41 and formula_42. If we multiply these out we will get formula_43. Therefore, formula_44.
If you want to use complex numbers to show that formula_45 you first must know that when multiplying angles you put the complex number to the power of the number that you are multiplying by. So formula_46 and since the real part and imaginary part are equal then, formula_47
Lehmer's measure.
One of the most important parameters that characterizes computational efficiency of the Machin-like formula is the Lehmer's measure, defined as 
In order to obtain the Lehmer's measure as small as possible, it is necessary to decrease the ratio of positive integers formula_49 in the arctangent arguments and to minimize the number of the terms in the Machin-like formula. Nowadays at formula_50 the smallest known Lehmer's measure is formula_51 due to H. Chien-Lih (1997), whose Machin-like formula is shown below. It is very common in the Machin-like formulas when all integers formula_52.
Two-term formulas.
In the special case where formula_50, there are exactly four solutions having only two terms. These are
Euler's:
Hermann's:
Hutton's (or Vega's):
and Machin's:
In the general case, where the value of formula_2 is not restricted, there are infinitely many other solutions. For example:
Example.
The adjacent diagram demonstrates the relationship between the arctangents and their areas. From the diagram, we have the following:
More terms.
The 2002 record for digits of , 1,241,100,000,000, was obtained by Yasumasa Kanada of Tokyo University. The calculation was performed on a 64-node Hitachi supercomputer with 1 terabyte of main memory, performing 2 trillion operations per second. The following two equations were both used:
Two equations are used so that one can check they both give the same result; it is helpful if the equations reuse some but not all of the arctangents because those need only be computed once - note the reuse of 57 and 239 above.
Machin-like formulae for can be constructed by finding a set of numbers where the prime factorisations of together use no more distinct primes than the number of elements in the set, and then using either linear algebra or the LLL basis-reduction algorithm to construct linear combinations of formula_62. For example, for the Størmer formula above, we have
so four terms using between them only the primes 2, 5, 13 and 61.
The most efficient currently known Machin-like formula pair discovered by Hwang Chien-Lih (黃見利) (2004) for computing are:
You will note that these formulae reuse all the same arctangents after the first one. They are constructed by looking for numbers where is divisible only by primes less than 101.
The most efficient currently known Machin-like formulas for computing are:
A further refinement is to use "Todd's Process", as described in; this leads to results such as
where the large prime 834312889110521 divides the of the last two indices.<br>
M. Wetherfield found 2004
Efficiency.
For large computations of formula_72, the binary splitting algorithm can be used to compute the arctangents much, much more quickly than by adding the terms in the Taylor series naively one at a time. In practical implementations such as y-cruncher, there is a relatively large constant overhead per term plus a time proportional to formula_73, and a point of diminishing returns appears beyond three or four arctangent terms in the sum; this is why the supercomputer calculation above used only a four-term version.
It is not the goal of this section to estimate the actual run time of any given algorithm. Instead, the intention is merely to devise a relative metric by which two algorithms can be compared against each other.
Let formula_74 be the number of digits to which formula_72 is to be calculated.
Let formula_76 be the number of terms in the Taylor series (see equation ).
Let formula_77 be the amount of time spent on each digit (for each term in the Taylor series).
The Taylor series will converge when:
Thus:
For the first term in the Taylor series, all formula_74 digits must be processed. In the last term of the Taylor series, however, there's only one digit remaining to be processed. In all of the intervening terms, the number of digits to be processed can be approximated by linear interpolation. Thus the total is given by:
The run time is given by:
Combining equations, the run time is given by:
Where formula_35 is a constant that combines all of the other constants. Since this is a relative metric, the value of formula_35 can be ignored.
The total time, across all the terms of equation , is given by:
formula_77 cannot be modelled accurately without detailed knowledge of the specific software. Regardless, we present one possible model.
The software spends most of its time evaluating the Taylor series from equation . The primary loop can be summarized in the following pseudo code:
In this particular model, it is assumed that each of these steps takes approximately the same amount of time. Depending on the software used, this may be a very good approximation or it may be a poor one.
The unit of time is defined such that one step of the pseudo code corresponds to one unit. To execute the loop, in its entirety, requires four units of time. formula_77 is defined to be four.
Note, however, that if formula_2 is equal to one, then step one can be skipped. The loop only takes three units of time. formula_77 is defined to be three.
As an example, consider the equation:
The following table shows the estimated time for each of the terms:
The total time is 0.75467 + 0.54780 + 0.60274 = 1.9052
Compare this with equation . The following table shows the estimated time for each of the terms:
The total time is 1.1191 + 0.8672 = 1.9863
The conclusion, based on this particular model, is that equation is slightly faster than equation , regardless of the fact that equation has more terms. This result is typical of the general trend. The dominant factor is the ratio between formula_2 and formula_3. In order to achieve a high ratio, it is necessary to add additional terms. Often, there is a net savings in time.