Gauss–Legendre algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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, 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 . 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 in 1999 to compute the first 200 billion decimal digits of , with results checked using Borwein's 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, 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 . 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 in 1999 to compute the first 200 billion decimal digits of , with results checked using Borwein's 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} is then approximated as: \pi \approx \frac{(a_{n+1}+b_{n+1})^2}{4t_{n+1}}.

The first five 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. \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. K(\cos \theta) E(\sin \theta ) + K(\sin \theta ) E(\cos \theta) - K(\cos \theta) K(\sin \theta) = {\pi \over 2}, for all \theta .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1355250971 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001355250971 · captured 1779300254.0 · version history

Cite this page as: encyclopegia.org, “Gauss–Legendre algorithm”, snapshot enwiki-001355250971. https://encyclopegia.org/a/gauss-legendre-algorithm

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.