Gauss-Legendre algorithm
|
|
The Gauss-Legendre algorithm is an algorithm to compute the digits 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 Salamin-Brent algorithm; it was independently discovered in 1976 by Eugene Salamin and Richard Brent. 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.
1. Initial value setting;
- <math>a = 1\qquad b = \frac{1}{\sqrt{2}}\qquad t = \frac{1}{4}\qquad p = 1<math>
2. Repeat the following instructions until the difference of a and b is within the desired accuracy:
- <math>x = \frac{a + b}{2}<math>
- <math>y = \sqrt{ab}<math>
- <math>t = t - p(a-x)^2<math>
- <math>a = x<math>
- <math>b = y<math>
- <math>p = 2p<math>
3. π is approximated with a, b and t as:
- <math>\pi \approx \frac{(a+b)^2}{4t}<math>
The algorithm has second order convergent nature, which essentially means that the number of correct digits doubles with each step of the algorithm.