- 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 overMachin-like formulas .The method is based on the individual work of
Carl Friedrich Gauss (1777–1855) andAdrien-Marie Legendre (1752–1833) combined with modern algorithms for multiplication andsquare root s. It repeatedly replaces two numbers by their arithmetic andgeometric mean , in order to approximate theirarithmetic-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 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 withBorwein's algorithm .1. Initial value setting:
:a_0 = 1qquad b_0 = frac{1}{sqrt{2qquad 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:
: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!.
3. π is approximated with a_n!, b_n! and t_n! as:
:pi approx frac{(a_n+b_n)^2}{4t_n}!.
The first three iterations give:
:3.140...!:3.14159264...!:3.14159265358979...!
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_0! and b_0!, is found by calculating the limit of the sequences a_{n+1}={a_n+b_n over 2}!, b_{n+1}=sqrt{a_n b_n}!, which both converge to the same limit.If a_0=1! and b_0=cosphi! then the limit is pi over 2K(sinphi)}! where K(k)! is the complete elliptic integral of the first kind:K(k) = int_0^{frac{pi}{2 frac{d heta}{sqrt{1-k^2 sin^2 heta!.
If c_0 = sinphi!, c_{i+1} = a_i - a_{i+1}!. then:sum_{i=0}^{infty} 2^{i-1} c_i^2 = 1 - {E(sinphi)over K(sinphi)}!where E(k)! be the complete elliptic integral of the second kind::E(k) = int_0^{frac{pi}{2sqrt {1-k^2 sin^2 heta} d heta!.Gauss knew of both of these results.Citation
last=Brent
first=Richard
author-link=Richard Brent (scientist)
publication-date=
date=
year=1975
title=Multiple-precision zero-finding methods and the complexity of elementary function evaluation
periodical=Analytic Computational Complexity
series=
publication-place=New York
place=
publisher=Academic Press
editor-last=Traub
editor-first=J F
volume=
issue=
pages=151–176
url=http://wwwmaths.anu.edu.au/~brent/pub/pub028.html
issn=
doi=
oclc=
accessdate=8 September 2007 ]Legendre’s identity
For phi! and heta! such that phi+ heta={1 over 2}pi! Legendre proved the identity::K(sin phi) E(sin heta ) + K(sin heta ) E(sin phi) - K(sin phi) K(sin heta) = {1 over 2}pi!
Gauss–Legendre method
The values phi= heta={piover 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!.
ee also
*
Borwein's algorithm References
Wikimedia Foundation. 2010.