Gauss–Legendre algorithm

The Gauss–Legendre algorithm is an algorithm to compute the digits of π. 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 roots. It repeatedly replaces two numbers by their 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;[1] it was independently discovered in 1975 by Richard Brent and 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:
    a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad t_0 = \frac{1}{4}\qquad p_0 = 1.\!
  2. Repeat the following instructions until the difference of a_n\! and b_n\! is within the desired accuracy:
    \begin{align} a_{n+1} & = \frac{a_n + b_n}{2}, \\ b_{n+1} & = \sqrt{a_n b_n}, \\ t_{n+1} & = t_n - p_n(a_{n}-a_{n+1})^2, \\ p_{n+1} & = 2p_n. \end{align}
  3. π is then approximated as:
    \pi \approx \frac{(a_{n+1}+b_{n+1})^2}{4t_{n+1}}.\!

The first three iterations give (approximations given up to and including the first incorrect digit):

3.140\dots\!
3.14159264\dots\!
3.1415926535897932382\dots\!

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, a0 and b0, is found by calculating the limit of the sequences

\begin{align} a_{n+1} & = \frac{a_n+b_n}{2}, \\ b_{n+1} & = \sqrt{a_n b_n}, \end{align}

which both converge to the same limit.
If a_0=1\! and b_0=\cos\varphi\! then the limit is {\pi \over 2K(\sin\varphi)}\! where K(k)\! is the complete elliptic integral of the first kind

K(k) = \int_0^{\pi/2} \frac{d\theta}{\sqrt{1-k^2 \sin^2\theta}}.\!

If c_0 = \sin\varphi\!, c_{i+1} = a_i - a_{i+1}\!. then

\sum_{i=0}^\infty 2^{i-1} c_i^2 = 1 - {E(\sin\varphi)\over K(\sin\varphi)}\!

where E(k)\! is the complete elliptic integral of the second kind:

E(k) = \int_0^{\pi/2}\sqrt {1-k^2 \sin^2\theta}\, d\theta.\!

Gauss knew of both of these results.[2] [3] [4]

Legendre’s identity

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

K(\sin \varphi) E(\sin \theta ) + K(\sin \theta ) E(\sin \varphi) - K(\sin \varphi) K(\sin \theta) = {1 \over 2}\pi.\![2]

Gauss–Euler method

The values \varphi=\theta={\pi\over 4}\! 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 a_0=1\! and b_0=\sin{\pi \over 4}=\frac{1}{\sqrt{2}}\!.[5]

See also

References

  1. ↑ Brent, Richard, Old and New Algorithms for pi, Letters to the Editor, Notices of the AMS 60(1), p. 7
  2. 1 2 Brent, Richard (1975), Traub, J F, ed., "Multiple-precision zero-finding methods and the complexity of elementary function evaluation", Analytic Computational Complexity (New York: Academic Press), pp. 151–176, retrieved 8 September 2007
  3. ↑ Salamin, Eugene, Computation of pi, Charles Stark Draper Laboratory ISS memo 74–19, 30 January 1974, Cambridge, Massachusetts
  4. ↑ Salamin, Eugene (1976), "Computation of pi Using Arithmetic–Geometric Mean", Mathematics of Computation 30 (135), pp. 565–570, ISSN 0025-5718
  5. ↑ Adlaj, Semjon, An eloquent formula for the perimeter of an ellipse, Notices of the AMS 59(8), p. 1096
This article is issued from Wikipedia - version of the Sunday, December 07, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.