Machin-like formula explained

In mathematics, Machin-like formulas are a popular technique for computing (the ratio of the circumference to the diameter of a circle) to a large number of digits. They are generalizations of John Machin's formula from 1706:

(\pi)/(4) = 4 \arctan (1)/(5) - \arctan (1)/(239)

which he used to compute to 100 decimal places.^{[1] [2]}

Machin-like formulas have the form

where

c _{0} is a positive integer, c _{n} are signed non-zero integers, and a _{n} and b _{n} are positive integers such that a _{n} < b _{n} .

These formulas are used in conjunction with Gregory's series, the Taylor series expansion for arctangent:

Derivation

The angle addition formula for arctangent asserts that

ifAll of the Machin-like formulas can be derived by repeated application of equation . As an example, we show the derivation of Machin's original formula one has:and consequentlyTherefore alsoand so finally$$\backslash frac\; =\; 4\; \backslash arctan\; \backslash frac\; -\; \backslash arctan\; \backslash frac.$$

An insightful way to visualize equation is to picture what happens when two complex numbers are multiplied together:

(b _{1} + a _{1} i ) ⋅ (b _{2} + a _{2} i ) = b _{1} b _{2} + a _{2} b _{1} i + a _{1} b _{2} i - a _{1} a _{2}

The angle associated with a complex number

(b _{n} + a _{n} i ) is given by:\arctan (a _{n})/(b _{n})

Thus, in equation, the angle associated with the product is:

\arctan (a _{1} b _{2} + a _{2} b _{1})/(b _{1} b _{2} - a _{1} a _{2})

Note that this is the same expression as occurs in equation . Thus equation can be interpreted as saying that multiplying two complex numbers means adding their associated angles (see multiplication of complex numbers).

The expression:

c _{n} \arctan (a _{n})/(b _{n})

is the angle associated with:

(b _{n} + a _{n} i ) ^{c _{n}}

Equation can be re-written as:

k ⋅ ( 1 + i ) ^{c _{0}} = \prod ^{N} _{n =1} (b _{n} + a _{n} i ) ^{c _{n}}

Here

k 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.^[3] For example, the angle of a complex number $(a\; +\; b\; \backslash mathrm)$ is given by $\backslash arctan\backslash frac$ and, when one multiplies complex numbers, one adds their angles. If $a=b$ then $\backslash arctan\backslash frac$ is 45 degrees or $\backslash frac$ radians. This means that if the real part and complex part are equal then the arctangent will equal $\backslash frac$. 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 $(2\; +\; \backslash mathrm)$ and $(3\; +\; \backslash mathrm)$. If we multiply these out we will get $(5\; +\; 5\; \backslash mathrm)$. Therefore, $\backslash arctan\backslash frac\; +\; \backslash arctan\backslash frac\; =\; \backslash frac$.

If you want to use complex numbers to show that $\backslash frac\; =\; 4\backslash arctan\backslash frac\; -\; \backslash arctan\backslash frac$ 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 $(5+\backslash mathrm)^4\; (239-\backslash mathrm)\; =\; (1+\backslash mathrm)\backslash cdot\; 2^2\backslash cdot\; 13^4$ and since the real part and imaginary part are equal then, $4\backslash arctan\backslash frac\; -\; \backslash arctan\backslash frac\; =\; \backslash frac~.$

Lehmer's measure

One of the most important parameters that characterize computational efficiency of a Machin-like formula is the Lehmer's measure, defined as^{[4] [5]}

{\it{ λ }} = \sum ^{N} _{n =1} (1)/(log _{10} (b _{n/a} _{n)}) .In order to obtain the Lehmer's measure as small as possible, it is necessary to decrease the ratio of positive integers a _{n/b} _{n} in the arctangent arguments and to minimize the number of the terms in the Machin-like formula. Nowadays at a _{n=1} the smallest known Lehmer's measure is λ ≈ 1 . 51244 due to H. Chien-Lih (1997),^[6] whose Machin-like formula is shown below. It is very common in the Machin-like formulas when all numerators a _{n} = 1 ~.

Two-term formulas

In the special case where the numerator

a _{n=1} , there are exactly four solutions having only two terms.^{[7] [8]} All four were found by John Machin in 1705–1706, but only one of them became widely known when it was published in William Jones's book Synopsis Palmariorum Matheseos, so the other three are often attributed to other mathematicians. These are

Euler's 1737 (known to Machin 1706):^{[9] [10]}

(\pi)/(4) = \arctan (1)/(2) + \arctan (1)/(3)

Hermann's 1706 (known to Machin 1706):^{[11] [10]}

(\pi)/(4) = 2 \arctan (1)/(2) - \arctan (1)/(7)

Hutton's or Vega's (known to Machin 1706):^{[8] [10]}

(\pi)/(4) = 2 \arctan (1)/(3) + \arctan (1)/(7)

and Machin's 1706:^{[1] [10]}

(\pi)/(4) = 4 \arctan (1)/(5) - \arctan (1)/(239) .

In the general case, where the value of a numerator

a _{n} is not restricted, there are infinitely many other solutions. For example:(\pi)/(4) = 22 \arctan (1)/(28) + \arctan (1744507482180328366854565127)/(98646395734210062276153190241239) or

Example

The adjacent diagram demonstrates the relationship between the arctangents and their areas. From the diagram, we have the following:

\begin{array}{ll} {\rm area}(PON)& = {\rm area}(MOF) = \pi x (\angle MOF)/(2 \pi) = \angle MEF = \arctan{ 1 \over 2 }\\ {\rm area}(POM)& = {\rm area}(NOF) = \arctan{ 1 \over 3 }\\ {\rm area}(POF)& = {\pi\over 4 } = \arctan{ 1 \over 2 } + \arctan{ 1 \over 3 }\\ {\rm area}(MON)& = \arctan{ 1 \over 7 }\\ \arctan{ 1 \over 2 }& = \arctan{ 1 \over 3 } + \arctan{ 1 \over 7 } , \end{array} a relation which can also be found by means of
the following calculation within the complex numbers( 3+ i ) ( 7+ i ) = 21-1 + ( 3+7 ) i = 10 ⋅ ( 2+ i ) .

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:

(\pi)/(4) = 12 \arctan (1)/(49) + 32 \arctan (1)/(57) - 5 \arctan (1)/(239) + 12 \arctan (1)/(110443)

Kikuo Takano (1982).

(\pi)/(4) = 44 \arctan (1)/(57) + 7 \arctan (1)/(239) - 12 \arctan (1)/(682) + 24 \arctan (1)/(12943)

F. C. M. Størmer (1896).

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 formulas 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 arctangents

\arctan \tfrac{ 1 }{b _{n}} of reciprocals of integer denominators b _{n} . For example, for the Størmer formula above, we have57 ^{2+1} = 2 ⋅ 5 ^{3} ⋅ 13 239 ^{2+1} = 2 ⋅ 13 ^{4} 682 ^{2+1} = 5 ^{3} ⋅ 61 ^{2} 12943 ^{2+1} = 2 ⋅ 5 ^{4} ⋅ 13 ^{3} ⋅ 61

so four terms using between them only the primes 2, 5, 13 and 61.

In 1993 Jörg Uwe Arndt^[12] found the 11-term formula:

\begin{align} (\pi)/(4) = & 36462 \arctan (1)/(390112) +135908 \arctan (1)/(485298) +274509 \arctan (1)/(683982) \\ & -39581 \arctan (1)/(1984933) +178477 \arctan (1)/(2478328) -114569 \arctan (1)/(3449051) \\ & -146571 \arctan (1)/(18975991) +61914 \arctan (1)/(22709274) -69044 \arctan (1)/(24208144) \\ & -89431 \arctan (1)/(201229582) -43938 \arctan (1)/(2189376182) \\ \end{align} using the set of 11 primes \{ 2 , 5 , 13 , 17 , 29 , 37 , 53 , 61 , 89 , 97 , 101 \} .

Another formula where 10 of the

\arctan -arguments are the same as above has been discovered by Hwang Chien-Lih (黃見利) (2004), so it is easier to check they both give the same result:\begin{align} (\pi)/(4) = & 36462 \arctan (1)/(51387) +26522 \arctan (1)/(485298) +19275 \arctan (1)/(683982) \\ & -3119 \arctan (1)/(1984933) -3833 \arctan (1)/(2478328) -5183 \arctan (1)/(3449051) \\ & -37185 \arctan (1)/(18975991) -11010 \arctan (1)/(22709274) +3880 \arctan (1)/(24208144) \\ & -16507 \arctan (1)/(201229582) -7476 \arctan (1)/(2189376182) \\ \end{align}

You will note that these formulas reuse all the same arctangents after the first one. They are constructed by looking for numbers where is divisible only by primes less than 102.

The most efficient currently known Machin-like formula for computing is:

\begin{align} (\pi)/(4) = & 183 \arctan (1)/(239) +32 \arctan (1)/(1023) -68 \arctan (1)/(5832) \\ & +12 \arctan (1)/(110443) -12 \arctan (1)/(4841182) -100 \arctan (1)/(6826318) \\ \end{align}

(Hwang Chien-Lih, 1997)

where the set of primes is

\{ 2 , 5 , 13 , 229 , 457 , 1201 \} .

A further refinement is to use "Todd's Process", as described in;^[5] this leads to results such as

\begin{align} (\pi)/(4) = & 183 \arctan (1)/(239) +32 \arctan (1)/(1023) -68 \arctan (1)/(5832) \\ & +12 \arctan (1)/(113021) -100 \arctan (1)/(6826318) \\ & -12 \arctan (1)/(33366019650) +12 \arctan (1)/(43599522992503626068) \\ \end{align}

(Hwang Chien-Lih, 2003)where the large prime 834312889110521 divides the of the last two indices.
M. Wetherfield found 2004

\begin{align} (\pi)/(4) = & 83 \arctan (1)/(107) +17 \arctan (1)/(1710) -22 \arctan (1)/(103697) \\ & -24 \arctan (1)/(2513489) -44 \arctan (1)/(18280007883) \\ & +12 \arctan (1)/(7939642926390344818) \\ & +22 \arctan (1)/(3054211727257704725384731479018) .\\ \end{align}

In Pi Day 2024, Matt Parker along with 400 volunteers used the following formula to hand calculate

\pi :\begin{align} (\pi)/(4) = & 1587 \arctan (1)/(2852) +295 \arctan (1)/(4193) +593 \arctan (1)/(4246) \\ & +359 \arctan (1)/(39307) +481 \arctan (1)/(55603) +625 \arctan (1)/(211050) \\ & -708 \arctan (1)/(390112) \end{align}

It was the biggest hand calculation of

\pi in a century. ^[13]

More methods

There are further methods to derive Machin-like formulas for

\pi with reciprocals of integers. One is given by the following formula:^[14] (\pi)/(4) = 2 ^{k-1} ⋅ \arctan (1)/(A _{k}) + \sum \limits ^{M} _{m =1} \arctan (1)/(\left \lfloor B _{k,m} \right \rfloor) + \arctan (1)/(B _{k,M+1}) , wherea _{0} : = 0 and recursivelya _{k} : = \sqrt{ 2 + a _{k} }, \; A_k := \left \lfloor \frac \right \rfloor andB _{k,1} : = (2)/(\left(\dfrac{A _{k+i}) {A _{k-i} } \right) ^{2 ^{k}} - i } - \mathrmand recursivelyB _{k,m} : = (1+ \left \lfloor B _{k,m} \right \rfloor B _{k,m})/(\left \lfloor B _{k,m} \right \rfloor - B _{k,m}) ~. E.g., for k = 4 and M = 5 we get:\begin{align} (\pi)/(4) = & 8 \arctan (1)/(10) - \arctan (1)/(84) - \arctan (1)/(21342) \\ & - \arctan (1)/(991268848) - \arctan (1)/(193018008592515208050) \\ & - \arctan (1)/(197967899896401851763240424238758988350338) \\ & - \arctan (1)/(117573868168175352930277752844194126767991915008537018836932014293678271636885792397) \end{align} This is verified by the following MuPAD code:z:=(10+I)^8*(84-I)*(21342-I)*(991268848-I)*(193018008592515208050-I)\ *(197967899896401851763240424238758988350338-I)\ *(117573868168175352930277752844194126767991915008537018836932014293678271636885792397-I):Re(z)-Im(z)0meaning\begin{align} z: = & ( 10+ i ) ^{8 ⋅ (84-i) ⋅ (21342-i) ⋅ (991268848-i) ⋅ (193018008592515208050-i)} \\ & ⋅ ( 197967899896401851763240424238758988350338- i ) \\ & ⋅ ( 117573868168175352930277752844194126767991915008537018836932014293678271636885792397- i ) \\ = & ( 1+ i ) ⋅ \Re(z) ~. \end{align}

Efficiency

For large computations of

\pi , 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 1 / log b _{n} , 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

N _{d} be the number of digits to which \pi is to be calculated.

Let

N _{t} be the number of terms in the Taylor series (see equation).

Let

u _{n} be the amount of time spent on each digit (for each term in the Taylor series).

The Taylor series will converge when:

\left(\left( (b _{n})/(a _{n}) \right) ^{2\right)} ^{N _{t}} = 10 ^{N _{d}}

Thus:

N _{t} = N _{d} (ln10)/(2 ln (b _{n})/(a _{n}))

For the first term in the Taylor series, all

N _{d} 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:(N _{d} N _{t})/(2)

The run time is given by:

time = (u _{n} N _{d} N _{t})/(2)

Combining equations, the run time is given by:

time = (u _{n} {N _{d})/(^{2}) ln 10 }{ 4 ln (b _{n})/(a _{n}) } = \frac

Where

k is a constant that combines all of the other constants. Since this is a relative metric, the value of k can be ignored.

The total time, across all the terms of equation, is given by:

time = \sum ^{N} _{n =1} (u _{n})/(ln (b _{n})/(a _{n})) u _{n} 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:

1 : term * = {a ^{2} _{n}} 2 : term / = - {b ^{2} _{n}} 3 : tmp = term / ( 2 *n +1 ) 4 : sum += tmp

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.

u _{n} is defined to be four.

Note, however, that if

a _{n} is equal to one, then step one can be skipped. The loop only takes three units of time. u _{n} is defined to be three.

As an example, consider the equation:

The following table shows the estimated time for each of the terms:

a _{n}	b _{n}	(b _{n})/(a _{n})	ln (b _{n})/(a _{n})	u _{n}	time
74684	14967113	200.41	5.3003	4	0.75467
1	239	239.00	5.4765	3	0.54780
20138	15351991	762.34	6.6364	4	0.60274

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:

a _{n}	b _{n}	(b _{n})/(a _{n})	ln (b _{n})/(a _{n})	u _{n}	time
24478	873121	35.670	3.5743	4	1.1191
685601	69049993	100.71	4.6123	4	0.8672

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

a _{n} and b _{n} . In order to achieve a high ratio, it is necessary to add additional terms. Often, there is a net savings in time.

External links

• • The constant π
• Machin's Merit at MathPages

Notes and References

1. Book: Jones, William . William Jones (mathematician) . 1706 . Synopsis Palmariorum Matheseos . London . J. Wale . 243, 263 . There are various other ways of finding the Lengths, or Areas of particular Curve Lines or Planes, which may very much facilitate the Practice; as for instance, in the Circle, the Diameter is to Circumference as 1 to
   \overline{\tfrac{ 16 } 5 - \tfrac 4 { 239 }} - \tfrac 13 \overline{\tfrac{ 16 }{ 5 ^{3}} - \tfrac 4 { 239 ^{3}} +} \tfrac 15 \overline{\tfrac{ 16 }{ 5 ^{5}} - \tfrac 4 { 239 ^{5}} -,} \&c. =
   . This Series (among others for the same purpose, and drawn from the same Principle) I receiv'd from the Excellent Analyst, and my much Esteem'd Friend Mr. John Machin; and by means thereof, Van Ceulens Number, or that in Art. 64.38. may be Examin'd with all desireable Ease and Dispatch..

   Reprinted in Book: Smith, David Eugene . 1929 . A Source Book in Mathematics . McGraw–Hill . William Jones: The First Use of for the Circle Ratio . https://archive.org/details/sourcebookinmath1929smit/page/346/ . 346–347 .

2. Book: Beckmann. Petr. A History Of Pi. 1971. The Golem Press. USA. 0-88029-418-3. 102. registration.
3. Størmer . Carl . Carl Størmer . 1897 . Sur l'application de la théorie des nombres entiers complexes a la solution en nombres rationnels $x\_1\backslash \; x\_2\; \backslash ldots\; x\_n$$c\_1\backslash \; c\_2\backslash ldots\; c\_n$$k$ de l'équation: $c\_1\; \backslash operatornamex\_1\; +$$c\_2\; \backslash operatornamex\_2\; +\; \backslash cdots\; +$$c\_n\; \backslash operatornamex\_n\; =$$k\backslash tfrac\backslash pi4$ . Archiv for Mathematik og Naturvidenskab . 19 . 3 . 1–95 .
4. On Arccotangent Relations for π . Lehmer . Derrick Henry . American Mathematical Monthly . 1938 . 45 . 10 . 657–664 . 10.2307/2302434 . 2302434.
5. The Enhancement of Machin's Formula by Todd's Process . Wetherfield . Michael . The Mathematical Gazette . 80 . 488 . 2016 . 333–344 . 10.2307/3619567 . 3619567. 126173230 .
6. More Machin-Type Identities . Chien-Lih . Hwang . The Mathematical Gazette . 81 . 490 . 3618793.
7. Størmer . Carl . Carl Størmer . 1896 . Solution complète en nombres entiers,,, et de l'équation $m\; \backslash operatorname\backslash tfrac1x\; +\; n\backslash operatorname\; \backslash tfrac1y\; =\; k\backslash tfrac\backslash pi4.$ . Skrifter udgivne af Videnskabsselskabet i Christiania . Mathematisk-naturvidenskabelig Klasse . 1895 . 11 . 1–21 .
8. Størmer . Carl . Carl Størmer . 1899 . Solution complète en nombres entiers de l'équation $m\; \backslash operatorname\backslash frac1x\; +\; n\; \backslash operatorname\backslash frac1y\; =\; k\backslash frac\backslash pi4$ . Complete solution in whole numbers of the equation ... . Bulletin de la Société Mathématique de France . 27 . 160–170 . fr . 10.24033/bsmf.603 . free .
9. Euler . Leonhard . Leonhard Euler . 1744 . written 1737 . De variis modis circuli quadraturam numeris proxime exprimendi . Commentarii academiae scientiarum Petropolitanae . 9 . 222–236 . E 74.
10. Tweddle . Ian . 1991 . John Machin and Robert Simson on Inverse-tangent Series for . Archive for History of Exact Sciences . 42 . 1 . 1–14 . 10.1007/BF00384331 . 41133896 .
11. Letter from Jakob Hermann to Gottfried Leibniz, 21 August 1706. Published in Book: Gerhardt . C.I. . 1859 . Leibnizens mathematische Schriften . 4 . XXII. Hermann an Leibniz. . 302–304 . H.W. Schmidt . https://archive.org/details/leibnizensmathe06leibgoog/page/302/ .
12. https://jjj.de/fxt/fxtbook.pdf Jörg Uwe Arndt: "Matters Computational"
13. The biggest hand calculation in a century! [Pi Day 2024] ]. en . 2024-04-02 . www.youtube.com.
14. https://arxiv.org/pdf/2108.07718.pdf (2021)