# 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 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 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; 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{aligned}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{aligned}} 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 quadratic convergence, which essentially means that the number of correct digits doubles with each iteration 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{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\[6pt]b_{n+1}&={\sqrt {a_{n}b_{n}}},\end{aligned}} which both converge to the same limit.
If $a_{0}=1$ and $b_{0}=\cos \varphi$ then the limit is ${\textstyle {\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$ and $K(k)=\int _{0}^{\pi /2}{\frac {d\theta }{\sqrt {1-k^{2}\sin ^{2}\theta }}}.$ Gauss knew of both of these results.  

### Legendre’s identity

For $\varphi$ and $\theta$ such that ${\textstyle \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 .$ Equivalently,
$\forall \varphi :K(\sin \varphi )[E(\cos \varphi )-K(\cos \varphi )]+K(\cos \varphi )E(\sin \varphi )={\frac {\pi }{2}}$ ### Elementary proof with integral calculus

The Gauss-Legendre algorithm can be proven without elliptic modular functions. This is done here and here using only integral calculus.