Gauss–Legendre algorithm

related topics
{math, number, function}

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 over Machin-like formulas.

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

Contents

Algorithm

1. Initial value setting:

2. Repeat the following instructions until the difference of a_n\! and b_n\! is within the desired accuracy:

3. π is then approximated as:

The first three iterations give:

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, a0 and b0, is found by calculating the limit of the sequences

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

If c_0 = \sin\varphi\!, c_{i+1} = a_i - a_{i+1}\!. then

Full article ▸

related documents
Catalan's constant
Integer sequence
Laurent polynomial
Probability axioms
Self-similarity
HTML scripting
Senary
Leaf node
Power associativity
NP-easy
Monoid ring
Timeline of programming languages
Wikipedia:Searching bug reports
Two-out-of-five code
Co-NP-complete
Church–Rosser theorem
Almost everywhere
EXPSPACE
Mary (programming language)
Measurable function
Gabriel Lamé
Digital Signature Algorithm
Weak entity
Sieve of Eratosthenes
Modus ponens
Ring homomorphism
Doubling the cube
JUnit
Pole (complex analysis)
Endomorphism ring