Gauss–Legendre algorithm

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 {{pi}}. However, it has some drawbacks (for example, it is computer memory-intensive) and therefore all record-breaking calculations for many years have used other methods, almost always the Chudnovsky algorithm. For details, see Chronology of computation of {{pi}}.

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;Brent, Richard, Old and New Algorithms for pi, Letters to the Editor, Notices of the AMS 60(1), p. 7 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 {{pi}} on September 18 to 20, 1999, and the results were checked with Borwein's algorithm.

Algorithm

Initial value setting: $a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad p_0 = 1\qquad t_0 = \frac{1}{4}.$
Repeat the following instructions until the difference between $a_{n+1}$ and $b_{n+1}$ is within the desired accuracy: $\begin{align}$

a_{n+1} & = \frac{a_n + b_n}{2}, \\ \\ b_{n+1} & = \sqrt{a_n b_n}, \\ \\ p_{n+1} & = 2p_n, \\ \\ t_{n+1} & = t_n - p_n(a_{n+1}-a_{n})^2. \\ \end{align}

{{pi}} 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$

: $3.14159265358979323846264338327950288419711\dots$

: $3.141592653589793238462643383279502884197169399375105820974944592307816406286208998625\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, a₀ and b₀, is found by calculating the limit of the sequences

: $\begin{align} a_{n+1} & = \frac{a_n+b_n}{2}, \\[6pt]
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 these two results.{{Citation

| last=Brent

| first=Richard

| author-link=Richard Brent (scientist)

| publication-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

| archive-date=23 July 2008

| archive-url=https://web.archive.org/web/20080723170157/http://wwwmaths.anu.edu.au/~brent/pub/pub028.html

| url-status=dead

}}

Salamin, Eugene, Computation of pi, Charles Stark Draper Laboratory ISS memo 74–19, 30 January 1974, Cambridge, Massachusetts

{{Citation

| last=Salamin

| first=Eugene

| author-link=Eugene Salamin (mathematician)

| publication-date=

| year=1976

| title=Computation of pi Using Arithmetic–Geometric Mean

| periodical=Mathematics of Computation

| series=

| publication-place=

| place=

| publisher=

| editor-last=

| editor-first=

| volume=30

| issue=135

| pages=565–570

| url=

| issn=0025-5718

| doi=10.2307/2005327

| jstor=2005327

| oclc=

| accessdate=

}}

= Legendre’s identity =

Legendre proved the following identity:

: $K(\cos \theta) E(\sin \theta ) + K(\sin \theta ) E(\cos \theta) - K(\cos \theta) K(\sin \theta) = {\pi \over 2},$

for all $\theta$ .

= Elementary proof with integral calculus =

The Gauss-Legendre algorithm can be proven to give results converging to π using only integral calculus. This is done here{{citation|title=Recent Calculations of π: The Gauss-Salamin Algorithm|last1=Lord|first1=Nick|doi=10.2307/3619132|year=1992|journal=The Mathematical Gazette|volume=76|issue=476|pages=231–242|jstor=3619132|s2cid=125865215 }} and here.{{citation|title=Easy Proof of Three Recursive π-Algorithms|last1=Milla|first1=Lorenz|arxiv=1907.04110|year=2019}}

References

Category:Pi algorithms