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 Machinlike formulas.
The method is based on the individual work of Carl Friedrich Gauss (1777–1855) and AdrienMarie 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 arithmeticgeometric 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 and is within the desired accuracy:
3. π is then approximated as:
The first three iterations give:
The algorithm has secondorder convergent nature, which essentially means that the number of correct digits doubles with each step of the algorithm.
Mathematical background
Limits of the arithmeticgeometric mean
The arithmeticgeometric mean of two numbers, a_{0} and b_{0}, is found by calculating the limit of the sequences
which both converge to the same limit. If and then the limit is where is the complete elliptic integral of the first kind
If , . then
Full article ▸
