fbpx
Wikipedia

Machin-like formula

In mathematics, Machin-like formulae 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:

which he used to compute π to 100 decimal places.[1][2]

Machin-like formulas have the form

 

 

 

 

(1)

where is a positive integer, are signed non-zero integers, and and are positive integers such that .

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

 

 

 

 

(2)

Derivation Edit

The angle addition formula for arctangent asserts that

 

 

 

 

 

(3)

if

 
All of the Machin-like formulas can be derived by repeated application of equation 3. As an example, we show the derivation of Machin's original formula one has:
 
and consequently
 
Therefore also
 
and so finally
 

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

 
 
 

 

 

 

 

(4)

The angle associated with a complex number   is given by:

 

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

 

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

The expression:

 

is the angle associated with:

 

Equation 1 can be re-written as:

 

Here   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 Edit

Other formulas may be generated using complex numbers.[3] For example, the angle of a complex number   is given by   and, when one multiplies complex numbers, one adds their angles. If   then   is 45 degrees or   radians. This means that if the real part and complex part are equal then the arctangent will equal  . 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   and  . If we multiply these out we will get  . Therefore,  .

If you want to use complex numbers to show that   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   and since the real part and imaginary part are equal then,  

Lehmer's measure Edit

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

 .

In order to obtain the Lehmer's measure as small as possible, it is necessary to decrease the ratio of positive integers   in the arctangent arguments and to minimize the number of the terms in the Machin-like formula. Nowadays at   the smallest known Lehmer's measure is   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  

Two-term formulas Edit

In the special case where the numerator  , 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]

 

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

 

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

 

and Machin's 1706:[1][10]

  .

In the general case, where the value of a numerator   is not restricted, there are infinitely many other solutions. For example:

 

or

 

 

 

 

 

(5)

Example Edit

 

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

 

a relation which can also be found by means of
the following calculation within the complex numbers

 

More terms Edit

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:

 
Kikuo Takano (1982).
 
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 b2+1 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   of reciprocals of integer denominators  . For example, for the Størmer formula above, we have

 
 
 
 

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:

 

using the set of 11 primes  

Another formula where 10 of the  -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:

 

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

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

 
(Hwang Chien-Lih, 1997)

where the set of primes is  

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

 
(Hwang Chien-Lih, 2003)

where the large prime 834312889110521 divides the bn2+1 of the last two indices.
M. Wetherfield found 2004

 

More methods Edit

There are further methods to derive Machin-like formulas for   with reciprocals of integers. One is given by the following formula:[13]

 

where

 

and recursively

 

and

 

and recursively

 

E.g., for   and   we get:

 

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) 0 

meaning

 

Efficiency Edit

For large computations of  , 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  , 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   be the number of digits to which   is to be calculated.

Let   be the number of terms in the Taylor series (see equation 2).

Let   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   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   is a constant that combines all of the other constants. Since this is a relative metric, the value of   can be ignored.

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

 

  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 2. 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.   is defined to be four.

Note, however, that if   is equal to one, then step one can be skipped. The loop only takes three units of time.   is defined to be three.

As an example, consider the equation:

 

 

 

 

 

(6)

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

           
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 5. The following table shows the estimated time for each of the terms:

           
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 6 is slightly faster than equation 5, regardless of the fact that equation 6 has more terms. This result is typical of the general trend. The dominant factor is the ratio between   and  . In order to achieve a high ratio, it is necessary to add additional terms. Often, there is a net savings in time.

References Edit

  1. ^ a b Jones, William (1706). Synopsis Palmariorum Matheseos. London: J. Wale. pp. 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
     
    3.14159, &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 Ceulen's Number, or that in Art. 64.38. may be Examin'd with all desireable Ease and Dispatch.

    Reprinted in Smith, David Eugene (1929). "William Jones: The First Use of π for the Circle Ratio". A Source Book in Mathematics. McGraw–Hill. pp. 346–347.

  2. ^ Beckmann, Petr (1971). A History Of Pi. USA: The Golem Press. p. 102. ISBN 0-88029-418-3.
  3. ^ Størmer, Carl (1897). "Sur l'application de la théorie des nombres entiers complexes a la solution en nombres rationnels     de l'équation:     ". Archiv for Mathematik og Naturvidenskab. 19 (3): 1–95.
  4. ^ Lehmer, Derrick Henry (1938). "On Arccotangent Relations for π". American Mathematical Monthly. 45 (10): 657–664. doi:10.2307/2302434. JSTOR 2302434.
  5. ^ a b Wetherfield, Michael (2016). "The Enhancement of Machin's Formula by Todd's Process". The Mathematical Gazette. 80 (488): 333–344. doi:10.2307/3619567. JSTOR 3619567. S2CID 126173230.
  6. ^ Chien-Lih, Hwang. "More Machin-Type Identities". The Mathematical Gazette. 81 (490). JSTOR 3618793.
  7. ^ Størmer, Carl (1896). "Solution complète en nombres entiers m, n, x, y et k de l'équation  ". Mathematisk-naturvidenskabelig Klasse. Skrifter udgivne af Videnskabsselskabet i Christiania. 1895 (11): 1–21.
  8. ^ a b Størmer, Carl (1899). "Solution complète en nombres entiers de l'équation  " [Complete solution in whole numbers of the equation ...]. Bulletin de la Société Mathématique de France (in French). 27: 160–170. doi:10.24033/bsmf.603.
  9. ^ Euler, Leonhard (1744) [written 1737]. "De variis modis circuli quadraturam numeris proxime exprimendi". Commentarii academiae scientiarum Petropolitanae. 9: 222–236. E 74.
  10. ^ a b c d Tweddle, Ian (1991). "John Machin and Robert Simson on Inverse-tangent Series for π". Archive for History of Exact Sciences. 42 (1): 1–14. doi:10.1007/BF00384331. JSTOR 41133896.
  11. ^ Letter from Jakob Hermann to Gottfried Leibniz, 21 August 1706. Published in Gerhardt, C.I., ed. (1859). "XXII. Hermann an Leibniz.". Leibnizens mathematische Schriften. Vol. 4. H.W. Schmidt. pp. 302–304.
  12. ^ Jörg Uwe Arndt: "Matters Computational" section 32.5.2, page 637.
  13. ^ https://arxiv.org/pdf/2108.07718.pdf (2021)

External links Edit

machin, like, formula, mathematics, popular, technique, computing, ratio, circumference, diameter, circle, large, number, digits, they, generalizations, john, machin, formula, from, 1706, arctan, arctan, displaystyle, frac, arctan, frac, arctan, frac, which, u. In mathematics Machin like formulae are a popular technique for computing p 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 p 4 4 arctan 1 5 arctan 1 239 displaystyle frac pi 4 4 arctan frac 1 5 arctan frac 1 239 which he used to compute p to 100 decimal places 1 2 Machin like formulas have the form c 0 p 4 n 1 N c n arctan a n b n displaystyle c 0 frac pi 4 sum n 1 N c n arctan frac a n b n 1 where c 0 displaystyle c 0 is a positive integer c n displaystyle c n are signed non zero integers and a n displaystyle a n and b n displaystyle b n are positive integers such that a n lt b n displaystyle a n lt b n These formulas are used in conjunction with Gregory s series the Taylor series expansion for arctangent arctan x n 0 1 n 2 n 1 x 2 n 1 x x 3 3 x 5 5 x 7 7 displaystyle arctan x sum n 0 infty frac 1 n 2n 1 x 2n 1 x frac x 3 3 frac x 5 5 frac x 7 7 cdots 2 Contents 1 Derivation 1 1 Using complex numbers 2 Lehmer s measure 3 Two term formulas 3 1 Example 4 More terms 5 More methods 6 Efficiency 7 References 8 External linksDerivation EditThe angle addition formula for arctangent asserts that arctan a 1 b 1 arctan a 2 b 2 arctan a 1 b 2 a 2 b 1 b 1 b 2 a 1 a 2 displaystyle arctan frac a 1 b 1 arctan frac a 2 b 2 arctan frac a 1 b 2 a 2 b 1 b 1 b 2 a 1 a 2 3 if p 2 lt arctan a 1 b 1 arctan a 2 b 2 lt p 2 displaystyle frac pi 2 lt arctan frac a 1 b 1 arctan frac a 2 b 2 lt frac pi 2 All of the Machin like formulas can be derived by repeated application of equation 3 As an example we show the derivation of Machin s original formula one has 2 arctan 1 5 arctan 1 5 arctan 1 5 arctan 1 5 1 5 5 5 1 1 arctan 10 24 arctan 5 12 displaystyle begin aligned 2 arctan frac 1 5 amp arctan frac 1 5 arctan frac 1 5 amp arctan frac 1 cdot 5 1 cdot 5 5 cdot 5 1 cdot 1 amp arctan frac 10 24 amp arctan frac 5 12 end aligned and consequently 4 arctan 1 5 2 arctan 1 5 2 arctan 1 5 arctan 5 12 arctan 5 12 arctan 5 12 5 12 12 12 5 5 arctan 120 119 displaystyle begin aligned 4 arctan frac 1 5 amp 2 arctan frac 1 5 2 arctan frac 1 5 amp arctan frac 5 12 arctan frac 5 12 amp arctan frac 5 cdot 12 5 cdot 12 12 cdot 12 5 cdot 5 amp arctan frac 120 119 end aligned Therefore also 4 arctan 1 5 p 4 4 arctan 1 5 arctan 1 1 4 arctan 1 5 arctan 1 1 arctan 120 119 arctan 1 1 arctan 120 1 1 119 119 1 120 1 arctan 1 239 displaystyle begin aligned 4 arctan frac 1 5 frac pi 4 amp 4 arctan frac 1 5 arctan frac 1 1 amp 4 arctan frac 1 5 arctan frac 1 1 amp arctan frac 120 119 arctan frac 1 1 amp arctan frac 120 cdot 1 1 cdot 119 119 cdot 1 120 cdot 1 amp arctan frac 1 239 end aligned and so finally p 4 4 arctan 1 5 arctan 1 239 displaystyle frac pi 4 4 arctan frac 1 5 arctan frac 1 239 An insightful way to visualize equation 3 is to picture what happens when two complex numbers are multiplied together b 1 a 1 i b 2 a 2 i displaystyle b 1 a 1 mathrm i cdot b 2 a 2 mathrm i b 1 b 2 a 2 b 1 i a 1 b 2 i a 1 a 2 displaystyle b 1 b 2 a 2 b 1 mathrm i a 1 b 2 mathrm i a 1 a 2 dd b 1 b 2 a 1 a 2 a 1 b 2 a 2 b 1 i displaystyle b 1 b 2 a 1 a 2 a 1 b 2 a 2 b 1 cdot mathrm i 4 dd The angle associated with a complex number b n a n i displaystyle b n a n mathrm i is given by arctan a n b n displaystyle arctan frac a n b n Thus in equation 4 the angle associated with the product is arctan a 1 b 2 a 2 b 1 b 1 b 2 a 1 a 2 displaystyle arctan frac 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 3 Thus equation 3 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 displaystyle c n arctan frac a n b n is the angle associated with b n a n i c n displaystyle b n a n mathrm i c n Equation 1 can be re written as k 1 i c 0 n 1 N b n a n i c n displaystyle k cdot 1 mathrm i c 0 prod n 1 N b n a n mathrm i c n Here k displaystyle 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 Edit Other formulas may be generated using complex numbers 3 For example the angle of a complex number a b i textstyle a b mathrm i is given by arctan b a textstyle arctan frac b a and when one multiplies complex numbers one adds their angles If a b textstyle a b then arctan b a textstyle arctan frac b a is 45 degrees or p 4 textstyle frac pi 4 radians This means that if the real part and complex part are equal then the arctangent will equal p 4 textstyle frac pi 4 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 i textstyle 2 mathrm i and 3 i textstyle 3 mathrm i If we multiply these out we will get 5 5 i textstyle 5 5 mathrm i Therefore arctan 1 2 arctan 1 3 p 4 textstyle arctan frac 1 2 arctan frac 1 3 frac pi 4 If you want to use complex numbers to show that p 4 4 arctan 1 5 arctan 1 239 textstyle frac pi 4 4 arctan frac 1 5 arctan frac 1 239 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 i 4 239 i 1 i 2 2 13 4 textstyle 5 mathrm i 4 239 mathrm i 1 mathrm i cdot 2 2 cdot 13 4 and since the real part and imaginary part are equal then 4 arctan 1 5 arctan 1 239 p 4 textstyle 4 arctan frac 1 5 arctan frac 1 239 frac pi 4 Lehmer s measure EditOne of the most important parameters that characterize computational efficiency of a Machin like formula is the Lehmer s measure defined as 4 5 l n 1 N 1 log 10 b n a n displaystyle it lambda sum n 1 N frac 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 displaystyle 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 displaystyle a n 1 the smallest known Lehmer s measure is l 1 51244 displaystyle lambda approx 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 displaystyle a n 1 Two term formulas EditIn the special case where the numerator a n 1 displaystyle 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 areEuler s 1737 known to Machin 1706 9 10 p 4 arctan 1 2 arctan 1 3 displaystyle frac pi 4 arctan frac 1 2 arctan frac 1 3 Hermann s 1706 known to Machin 1706 11 10 p 4 2 arctan 1 2 arctan 1 7 displaystyle frac pi 4 2 arctan frac 1 2 arctan frac 1 7 Hutton s or Vega s known to Machin 1706 8 10 p 4 2 arctan 1 3 arctan 1 7 displaystyle frac pi 4 2 arctan frac 1 3 arctan frac 1 7 and Machin s 1706 1 10 p 4 4 arctan 1 5 arctan 1 239 displaystyle frac pi 4 4 arctan frac 1 5 arctan frac 1 239 In the general case where the value of a numerator a n displaystyle a n is not restricted there are infinitely many other solutions For example p 4 22 arctan 1 28 arctan 1744507482180328366854565127 98646395734210062276153190241239 displaystyle frac pi 4 22 arctan frac 1 28 arctan frac 1744507482180328366854565127 98646395734210062276153190241239 or p 4 22 arctan 24478 873121 17 arctan 685601 69049993 displaystyle frac pi 4 22 arctan frac 24478 873121 17 arctan frac 685601 69049993 5 Example Edit The adjacent diagram demonstrates the relationship between the arctangents and their areas From the diagram we have the following a r e a P O N a r e a M O F p M O F 2 p M E F arctan 1 2 a r e a P O M a r e a N O F arctan 1 3 a r e a P O F p 4 arctan 1 2 arctan 1 3 a r e a M O N arctan 1 7 arctan 1 2 arctan 1 3 arctan 1 7 displaystyle begin array ll rm area PON amp rm area MOF pi times frac angle MOF 2 pi angle MEF arctan 1 over 2 rm area POM amp rm area NOF arctan 1 over 3 rm area POF amp pi over 4 arctan 1 over 2 arctan 1 over 3 rm area MON amp arctan 1 over 7 arctan 1 over 2 amp arctan 1 over 3 arctan 1 over 7 end array a relation which can also be found by means ofthe following calculation within the complex numbers 3 i 7 i 21 1 3 7 i 10 2 i displaystyle 3 mathrm i 7 mathrm i 21 1 3 7 mathrm i 10 cdot 2 mathrm i More terms EditThe 2002 record for digits of p 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 p 4 12 arctan 1 49 32 arctan 1 57 5 arctan 1 239 12 arctan 1 110443 displaystyle frac pi 4 12 arctan frac 1 49 32 arctan frac 1 57 5 arctan frac 1 239 12 arctan frac 1 110443 Kikuo Takano 1982 p 4 44 arctan 1 57 7 arctan 1 239 12 arctan 1 682 24 arctan 1 12943 displaystyle frac pi 4 44 arctan frac 1 57 7 arctan frac 1 239 12 arctan frac 1 682 24 arctan frac 1 12943 F C M Stormer 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 p can be constructed by finding a set of numbers where the prime factorisations of b2 1 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 1 b n displaystyle arctan frac 1 b n of reciprocals of integer denominators b n displaystyle b n For example for the Stormer formula above we have 57 2 1 2 5 3 13 displaystyle 57 2 1 2 cdot 5 3 cdot 13 239 2 1 2 13 4 displaystyle 239 2 1 2 cdot 13 4 682 2 1 5 3 61 2 displaystyle 682 2 1 5 3 cdot 61 2 12943 2 1 2 5 4 13 3 61 displaystyle 12943 2 1 2 cdot 5 4 cdot 13 3 cdot 61 so four terms using between them only the primes 2 5 13 and 61 In 1993 Jorg Uwe Arndt 12 found the 11 term formula p 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 displaystyle begin aligned frac pi 4 amp 36462 arctan frac 1 390112 135908 arctan frac 1 485298 274509 arctan frac 1 683982 amp 39581 arctan frac 1 1984933 178477 arctan frac 1 2478328 114569 arctan frac 1 3449051 amp 146571 arctan frac 1 18975991 61914 arctan frac 1 22709274 69044 arctan frac 1 24208144 amp 89431 arctan frac 1 201229582 43938 arctan frac 1 2189376182 end aligned using the set of 11 primes 2 5 13 17 29 37 53 61 89 97 101 displaystyle 2 5 13 17 29 37 53 61 89 97 101 Another formula where 10 of the arctan displaystyle 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 p 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 displaystyle begin aligned frac pi 4 amp 36462 arctan frac 1 51387 26522 arctan frac 1 485298 19275 arctan frac 1 683982 amp 3119 arctan frac 1 1984933 3833 arctan frac 1 2478328 5183 arctan frac 1 3449051 amp 37185 arctan frac 1 18975991 11010 arctan frac 1 22709274 3880 arctan frac 1 24208144 amp 16507 arctan frac 1 201229582 7476 arctan frac 1 2189376182 end aligned You will note that these formulas reuse all the same arctangents after the first one They are constructed by looking for numbers where b2 1 is divisible only by primes less than 102 The most efficient currently known Machin like formula for computing p is p 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 displaystyle begin aligned frac pi 4 amp 183 arctan frac 1 239 32 arctan frac 1 1023 68 arctan frac 1 5832 amp 12 arctan frac 1 110443 12 arctan frac 1 4841182 100 arctan frac 1 6826318 end aligned Hwang Chien Lih 1997 where the set of primes is 2 5 13 229 457 1201 displaystyle 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 p 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 displaystyle begin aligned frac pi 4 amp 183 arctan frac 1 239 32 arctan frac 1 1023 68 arctan frac 1 5832 amp 12 arctan frac 1 113021 100 arctan frac 1 6826318 amp 12 arctan frac 1 33366019650 12 arctan frac 1 43599522992503626068 end aligned Hwang Chien Lih 2003 where the large prime 834312889110521 divides the bn2 1 of the last two indices M Wetherfield found 2004 p 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 displaystyle begin aligned frac pi 4 amp 83 arctan frac 1 107 17 arctan frac 1 1710 22 arctan frac 1 103697 amp 24 arctan frac 1 2513489 44 arctan frac 1 18280007883 amp 12 arctan frac 1 7939642926390344818 amp 22 arctan frac 1 3054211727257704725384731479018 end aligned More methods EditThere are further methods to derive Machin like formulas for p displaystyle pi with reciprocals of integers One is given by the following formula 13 p 4 2 k 1 arctan 1 A k m 1 M arctan 1 B k m arctan 1 B k M 1 displaystyle frac pi 4 2 k 1 cdot arctan frac 1 A k sum limits m 1 M arctan frac 1 left lfloor B k m right rfloor arctan frac 1 B k M 1 where a 0 0 displaystyle a 0 0 and recursively a k 2 a k 1 A k a k 2 a k 1 displaystyle a k sqrt 2 a k 1 A k left lfloor frac a k sqrt 2 a k 1 right rfloor and B k 1 2 A k i A k i 2 k 1 i i displaystyle B k 1 frac 2 left dfrac A k mathrm i A k mathrm i right 2 k 1 mathrm i mathrm i and recursively B k m 1 B k m 1 B k m 1 B k m 1 B k m 1 displaystyle B k m frac 1 left lfloor B k m 1 right rfloor B k m 1 left lfloor B k m 1 right rfloor B k m 1 E g for k 4 displaystyle k 4 and M 5 displaystyle M 5 we get p 4 8 arctan 1 10 arctan 1 84 arctan 1 21342 arctan 1 991268848 arctan 1 193018008592515208050 arctan 1 197967899896401851763240424238758988350338 arctan 1 117573868168175352930277752844194126767991915008537018836932014293678271636885792397 displaystyle begin aligned frac pi 4 amp 8 arctan frac 1 10 arctan frac 1 84 arctan frac 1 21342 amp arctan frac 1 991268848 arctan frac 1 193018008592515208050 amp arctan frac 1 197967899896401851763240424238758988350338 amp arctan frac 1 117573868168175352930277752844194126767991915008537018836932014293678271636885792397 end aligned 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 0 meaning z 10 i 8 84 i 21342 i 991268848 i 193018008592515208050 i 197967899896401851763240424238758988350338 i 117573868168175352930277752844194126767991915008537018836932014293678271636885792397 i 1 i ℜ z displaystyle begin aligned z amp 10 mathrm i 8 cdot 84 mathrm i cdot 21342 mathrm i cdot 991268848 mathrm i cdot 193018008592515208050 mathrm i amp cdot 197967899896401851763240424238758988350338 mathrm i amp cdot 117573868168175352930277752844194126767991915008537018836932014293678271636885792397 mathrm i amp 1 mathrm i cdot Re z end aligned Efficiency EditFor large computations of p displaystyle 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 displaystyle 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 displaystyle N d be the number of digits to which p displaystyle pi is to be calculated Let N t displaystyle N t be the number of terms in the Taylor series see equation 2 Let u n displaystyle u n be the amount of time spent on each digit for each term in the Taylor series The Taylor series will converge when b n a n 2 N t 10 N d displaystyle left left frac b n a n right 2 right N t 10 N d Thus N t N d ln 10 2 ln b n a n displaystyle N t N d quad frac ln 10 2 ln frac b n a n For the first term in the Taylor series all N d displaystyle 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 displaystyle frac N d N t 2 The run time is given by t i m e u n N d N t 2 displaystyle mathit time frac u n N d N t 2 Combining equations the run time is given by t i m e u n N d 2 ln 10 4 ln b n a n k u n ln b n a n displaystyle mathit time frac u n N d 2 ln 10 4 ln frac b n a n frac k u n ln frac b n a n Where k displaystyle k is a constant that combines all of the other constants Since this is a relative metric the value of k displaystyle k can be ignored The total time across all the terms of equation 1 is given by t i m e n 1 N u n ln b n a n displaystyle mathit time sum n 1 N frac u n ln frac b n a n u n displaystyle 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 2 The primary loop can be summarized in the following pseudo code 1 t e r m a n 2 displaystyle 1 quad mathit term quad quad a n 2 dd 2 t e r m b n 2 displaystyle 2 quad mathit term quad quad b n 2 dd 3 t m p t e r m 2 n 1 displaystyle 3 quad mathit tmp quad quad mathit term quad quad 2 n 1 dd 4 s u m t m p displaystyle 4 quad mathit sum quad quad mathit tmp dd 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 displaystyle u n is defined to be four Note however that if a n displaystyle a n is equal to one then step one can be skipped The loop only takes three units of time u n displaystyle u n is defined to be three As an example consider the equation p 4 44 arctan 74684 14967113 139 arctan 1 239 12 arctan 20138 15351991 displaystyle frac pi 4 44 arctan frac 74684 14967113 139 arctan frac 1 239 12 arctan frac 20138 15351991 6 The following table shows the estimated time for each of the terms a n displaystyle a n b n displaystyle b n b n a n displaystyle frac b n a n ln b n a n displaystyle ln frac b n a n u n displaystyle u n t i m e displaystyle mathit time 74684 14967113 200 41 5 3003 4 0 754671 239 239 00 5 4765 3 0 5478020138 15351991 762 34 6 6364 4 0 60274The total time is 0 75467 0 54780 0 60274 1 9052Compare this with equation 5 The following table shows the estimated time for each of the terms a n displaystyle a n b n displaystyle b n b n a n displaystyle frac b n a n ln b n a n displaystyle ln frac b n a n u n displaystyle u n t i m e displaystyle mathit time 24478 873121 35 670 3 5743 4 1 1191685601 69049993 100 71 4 6123 4 0 8672The total time is 1 1191 0 8672 1 9863The conclusion based on this particular model is that equation 6 is slightly faster than equation 5 regardless of the fact that equation 6 has more terms This result is typical of the general trend The dominant factor is the ratio between a n displaystyle a n and b n displaystyle b n In order to achieve a high ratio it is necessary to add additional terms Often there is a net savings in time References Edit a b Jones William 1706 Synopsis Palmariorum Matheseos London J Wale pp 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 16 5 4 239 1 3 16 5 3 4 239 3 1 5 16 5 5 4 239 5 amp c displaystyle overline tfrac 16 5 tfrac 4 239 tfrac 1 3 overline tfrac 16 5 3 tfrac 4 239 3 tfrac 1 5 overline tfrac 16 5 5 tfrac 4 239 5 amp c 3 14159 amp c p 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 Ceulen s Number or that in Art 64 38 may be Examin d with all desireable Ease and Dispatch Reprinted in Smith David Eugene 1929 William Jones The First Use of p for the Circle Ratio A Source Book in Mathematics McGraw Hill pp 346 347 Beckmann Petr 1971 A History Of Pi USA The Golem Press p 102 ISBN 0 88029 418 3 Stormer Carl 1897 Sur l application de la theorie des nombres entiers complexes a la solution en nombres rationnels x 1 x 2 x n textstyle x 1 x 2 ldots x n c 1 c 2 c n textstyle c 1 c 2 ldots c n k textstyle k de l equation c 1 a r c t g x 1 textstyle c 1 operatorname arc tg x 1 c 2 a r c t g x 2 textstyle c 2 operatorname arc tg x 2 cdots c n a r c t g x n textstyle c n operatorname arc tg x n k p 4 textstyle k tfrac pi 4 Archiv for Mathematik og Naturvidenskab 19 3 1 95 Lehmer Derrick Henry 1938 On Arccotangent Relations for p American Mathematical Monthly 45 10 657 664 doi 10 2307 2302434 JSTOR 2302434 a b Wetherfield Michael 2016 The Enhancement of Machin s Formula by Todd s Process The Mathematical Gazette 80 488 333 344 doi 10 2307 3619567 JSTOR 3619567 S2CID 126173230 Chien Lih Hwang More Machin Type Identities The Mathematical Gazette 81 490 JSTOR 3618793 Stormer Carl 1896 Solution complete en nombres entiers m n x y et k de l equation m a r c t g 1 x n a r c t g 1 y k p 4 textstyle m operatorname arc tg tfrac 1 x n operatorname arc tg tfrac 1 y k tfrac pi 4 Mathematisk naturvidenskabelig Klasse Skrifter udgivne af Videnskabsselskabet i Christiania 1895 11 1 21 a b Stormer Carl 1899 Solution complete en nombres entiers de l equation m a r c t a n g 1 x n a r c t a n g 1 y k p 4 textstyle m operatorname arc tang frac 1 x n operatorname arc tang frac 1 y k frac pi 4 Complete solution in whole numbers of the equation Bulletin de la Societe Mathematique de France in French 27 160 170 doi 10 24033 bsmf 603 Euler Leonhard 1744 written 1737 De variis modis circuli quadraturam numeris proxime exprimendi Commentarii academiae scientiarum Petropolitanae 9 222 236 E 74 a b c d Tweddle Ian 1991 John Machin and Robert Simson on Inverse tangent Series for p Archive for History of Exact Sciences 42 1 1 14 doi 10 1007 BF00384331 JSTOR 41133896 Letter from Jakob Hermann to Gottfried Leibniz 21 August 1706 Published in Gerhardt C I ed 1859 XXII Hermann an Leibniz Leibnizens mathematische Schriften Vol 4 H W Schmidt pp 302 304 Jorg Uwe Arndt Matters Computational section 32 5 2 page 637 https arxiv org pdf 2108 07718 pdf 2021 External links EditWeisstein Eric W Machin like formulas MathWorld The constant p Machin s Merit at MathPages Retrieved from https en wikipedia org w index php title Machin like formula amp oldid 1168690344, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.