Content deleted Content added
m tm |
No edit summary |
||
| (98 intermediate revisions by 62 users not shown) | |||
Line 1:
{{Short description|Quickly converging computation of π}}
The '''Gauss–Legendre algorithm''' is an [[algorithm]] to compute the digits of [[Pi|{{pi}}]]. It is notable for being rapidly convergent, with only 25 iterations producing 45 million correct digits of {{pi}}. However, it has some drawbacks (for example, it is [[Random-access_memory|computer memory]]-intensive) and therefore all record-breaking calculations for many years have used other methods, almost always the [[Chudnovsky algorithm]]. For details, see [[chronology of computation of π|Chronology of computation of {{pi}}]].
The method is based on the individual work of [[Carl Friedrich Gauss]] (1777–1855) and [[Adrien-Marie Legendre]] (1752–1833) combined with modern algorithms for multiplication and [[square root]]s. It repeatedly replaces two numbers by their [[arithmetic mean|arithmetic]] and [[geometric mean]], in order to approximate their [[arithmetic-geometric mean]].
The version presented below is also known as the '''Gauss–Euler''', '''Brent–Salamin''' (or '''Salamin–Brent''') '''algorithm''';<ref>[[Richard Brent (scientist)|Brent, Richard]], ''Old and New Algorithms for pi'', Letters to the Editor, Notices of the AMS 60(1), p. 7</ref> it was independently discovered in 1975 by [[Richard Brent (scientist)
== Algorithm ==
# Initial value setting: <math display="block">a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad p_0 = 1\qquad t_0 = \frac{1}{4}.</math>
# Repeat the following instructions until the difference between <math>a_{n+1}</math> and <math>b_{n+1}</math> is within the desired accuracy: <math display="block"> \begin{align}
a_{n+1} & = \frac{a_n + b_n}{2}, \\
\\
b_{n+1} & = \sqrt{a_n b_n}, \\
\\
p_{n+1} & = 2p_n, \\
\\
t_{n+1} & = t_n - p_n(a_{n+1}-a_{n})^2. \\
\end{align}
</math>
# {{pi}} is then approximated as: <math display="block">\pi \approx \frac{(a_{n+1}+b_{n+1})^2}{4t_{n+1}}.</math>
The first three iterations give (approximations given up to and including the first incorrect digit):
:<math>3.140\dots</math>
:<math>3.14159264\dots</math>
:<math>3.1415926535897932382\dots</math>
:<math>3.14159265358979323846264338327950288419711\dots</math>
:<math>3.141592653589793238462643383279502884197169399375105820974944592307816406286208998625\dots</math>
The algorithm has [[quadratic convergence]], which essentially means that the number of correct digits doubles with each [[iteration]] of the algorithm.
== Mathematical background ==
=== Limits of the arithmetic–geometric mean ===
The [[arithmetic–geometric mean]] of two numbers, a<sub>0</sub> and b<sub>0</sub>, is found by calculating the limit of the sequences
:<math>\
b_{n+1} & = \sqrt{a_n b_n},
\end{align}
</math>
which both converge to the same limit.<br />
If <math>a_0=1</math> and <math>b_0=\cos\varphi</math> then the limit is <math display="inline">{\pi \over 2K(\sin\varphi)}</math> where <math>K(k)</math> is the [[Elliptic integral#Complete elliptic integral of the first kind|complete elliptic integral of the first kind]]
:<math>K(k) = \int_0^{\pi/2} \frac{d\theta}{\sqrt{1-k^2 \sin^2\theta}}.</math>
If <math>c_0 = \sin\varphi</math>, <math>c_{i+1} = a_i - a_{i+1}</math>, then
:<math>\sum_{i=0}^\infty 2^{i-1} c_i^2 = 1 - {E(\sin\varphi)\over K(\sin\varphi)}</math>
where <math>E(k)</math> is the [[Elliptic integral#Complete elliptic integral of the second kind|complete elliptic integral of the second kind]]:
:<math>E(k) = \int_0^{\pi/2}\sqrt {1-k^2 \sin^2\theta}\; d\theta</math>
Gauss knew of these two results.<ref name="brent">{{Citation
| last=Brent
| first=Richard
| author-link=Richard Brent (scientist)
| publication-date=
| year=1975
| title=Multiple-precision zero-finding methods and the complexity of elementary function evaluation
Line 63 ⟶ 74:
| doi=
| oclc=
| accessdate=
| archive-date=23 July 2008
| archive-url=https://web.archive.org/web/20080723170157/http://wwwmaths.anu.edu.au/~brent/pub/pub028.html
| url-status=dead
}}</ref>
<ref name="salamin1">[[Eugene Salamin (mathematician)|Salamin, Eugene]], ''Computation of pi'', Charles Stark Draper Laboratory ISS memo 74–19, 30 January 1974, Cambridge, Massachusetts</ref>
<ref name="salamin2">{{Citation
| last=Salamin
| first=Eugene
| author-link=Eugene Salamin (mathematician)
| publication-date=
| year=1976
| title=Computation of pi Using Arithmetic–Geometric Mean
| periodical=Mathematics of Computation
| series=
| publication-place=
| place=
| publisher=
| editor-last=
| editor-first=
| volume=30
| issue=135
| pages=565–570
| url=
| issn=0025-5718
| doi=10.2307/2005327
| jstor=2005327
| oclc=
| accessdate=
}}</ref>
=== Legendre’s identity ===
Legendre proved the following identity:
:<math display="block">K(\cos \theta) E(\sin \theta ) + K(\sin \theta ) E(\cos \theta) - K(\cos \theta) K(\sin \theta) = {\pi \over 2},</math>
for all <math>\theta</math>.<ref name="brent" />
=== Elementary proof with integral calculus ===
The Gauss-Legendre algorithm can be proven to give results converging to <math>\pi</math> using only integral calculus. This is done here<ref>{{citation|title=Recent Calculations of π: The Gauss-Salamin Algorithm|last1=Lord|first1=Nick|doi=10.2307/3619132|year=1992|journal=The Mathematical Gazette|volume=76|issue=476|pages=231–242|jstor=3619132|s2cid=125865215 }}</ref> and here.<ref>{{citation|title=Easy Proof of Three Recursive π-Algorithms|last1=Milla|first1=Lorenz|arxiv=1907.04110|year=2019}}</ref>
== See also ==
* [[Numerical approximations of π|Numerical approximations of {{pi}}]]
== References ==
{{reflist}}
{{DEFAULTSORT:Gauss-Legendre algorithm}}
[[Category:Pi algorithms]]
| |||