Gauss–Legendre algorithm: Difference between revisions

Revision as of 10:04, 27 December 2018

Revision as of 19:17, 5 April 2019

Line 1:

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, the drawback is that it is [[Random-access_memory|computer memory]]-intensive and therefore sometimes [[Machin-like formulas]] are used instead.

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)|Richard Brent]] and [[Eugene Salamin (mathematician)|Eugene Salamin]]. It was used to compute the first 206,158,430,000 decimal digits of π{{pi}} on September 18 to 20, 1999, and the results were checked with [[Borwein's algorithm]].

== Algorithm ==

Line 13:

\end{align}

</math>

# π{{pi}} is then approximated as:<br /><math>\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):

Line 105:

== See also ==

* [[Numerical approximations of π|Numerical approximations of {{pi}}]]

== References ==