- Gauss–Legendre algorithm
The

**Gauss–Legendre algorithm**is analgorithm 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 andEugene 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.*

### Look at other dictionaries:

**Adrien-Marie Legendre**— Pour les articles homonymes, voir Legendre. Adrien Marie Legendre Portrait charge de Adrien Marie Legendre[1] … Wikipédia en Français**Adrien-Marie Legendre**— Infobox Scientist name = Adrien Marie Legendre caption = Adrien Marie Legendre birth date = birth date|1752|9|18|mf=y birth place = Paris, France death date = death date and age|1833|1|10|1752|9|18|mf=y death place = Paris, France residence =… … Wikipedia**List of topics named after Carl Friedrich Gauss**— Carl Friedrich Gauss (1777 ndash; 1855) is the eponym of all of the topics listed below. Topics including Gauss *Carl Friedrich Gauss Prize, a mathematics award *Degaussing, to demagnetize an object *Gauss (unit), a unit of magnetic field (B)… … Wikipedia**Borwein's algorithm**— In mathematics, Borwein s algorithm is an algorithm devised by Jonathan and Peter Borwein to calculate the value of 1/ pi;. The most prominent and oft used one is explained under the first section.Borwein s algorithmStart out by setting: a 0 = 6… … Wikipedia**Approximations of π**— Timeline of approximations for pi … Wikipedia**List of numerical analysis topics**— This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra … Wikipedia**List of mathematics articles (G)**— NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… … Wikipedia**List of algorithms**— The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia**Computing π**— Similarly, the more complex approximations of π given below involve repeated calculations of some sort, yielding closer and closer approximations with increasing numbers of calculations.Continued fractionsBesides its simple continued fraction… … Wikipedia**Numerical approximations of π**— This page is about the history of numerical approximations of the mathematical constant pi;. There is a summarizing table at chronology of computation of pi;. See also history of pi; for other aspects of the evolution of our knowledge about… … Wikipedia