Gauss–Legendre algorithm: Difference between revisions

Revision as of 18:26, 10 September 2009

Revision as of 16:11, 28 November 2009

Line 1:

The '''Gauss–Legendre algorithm''' is an [[algorithm]] to compute the digits of [[Pi|ππ]]. It is notable for being rapidly convergent, with only 25 iterations producing 45 million correct digits of ππ. However, the drawback is that it is memory intensive and it is therefore sometimes not used over [[Machin-like formulas]].

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 '''Brent–Salamin (or Salamin–Brent) algorithm'''; 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 ππ on September 18 to 20, 1999, and the results were checked with [[Borwein's algorithm]].

== Algorithm ==

1. Initial value setting:

Line 20:

</math>

3. &pi;π is then approximated as:

:<math>\pi \approx \frac{(a_n+b_n)^2}{4t_n}.\!</math>

Line 32:

The algorithm has second-order convergent nature, which essentially means that the number of correct digits doubles with each step of the algorithm.

== Mathematical background ==

=== Limits of the arithmetic-geometric mean ===

The [[arithmetic-geometric mean]] of two numbers, a₀ and b₀, is found by calculating the limit of the sequences

Line 106:

}}</ref>

=== Legendre’s identity ===

For <math>\varphi\!</math> and <math>\theta\!</math> such that <math>\varphi+\theta={1 \over 2}\pi\!</math> Legendre proved the identity:

:<math>K(\sin \varphi) E(\sin \theta ) + K(\sin \theta ) E(\sin \varphi) - K(\sin \varphi) K(\sin \theta) = {1 \over 2}\pi\!</math><ref name="brent" />

=== Gauss–Legendre method ===

The values <math>\varphi=\theta={\pi\over 4}\!</math> can be substituted into Legendre’s identity and the approximations to K, E can be found by terms in the sequences for the arithmetic geometric mean with <math>a_0=1\!</math> and <math>b_0=\sin{\pi \over 4}=\frac{1}{\sqrt{2}}\!</math>.<ref name="brent" />

== References ==

{{reflist}}

Line 121:

[[es:Algoritmo de Gauss-Legendre]]

[[he:אלגוריתם גאוס-לז'נדר]]

[[it:Algoritmo di Gauss-Legendre]]

[[he:אלגוריתם גאוס-לז'נדר]]

[[nl:Algoritme van Gauss-Legendre]]

[[ja:ガウス＝ルジャンドルのアルゴリズム]]

[[zh:高斯-勒让德算法]]