Gauss-Legendre algorithm
From Free net encyclopedia
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 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.
1. Initial value setting:
- <math>a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad t_0 = \frac{1}{4}\qquad p_0 = 1</math>
2. Repeat the following instructions until the difference of <math>a_n</math> and <math>b_n</math> is within the desired accuracy:
- <math>x_{n+1} = \frac{a_n + b_n}{2} \,</math>
- <math>y_{n+1} = \sqrt{a_n b_n} \,</math>
- <math>t_{n+1} = t_n - p_n(a_n - x_{n+1})^2 \,</math>
- <math>a_{n+1} = x_{n+1} \,</math>
- <math>b_{n+1} = y_{n+1} \,</math>
- <math>p_{n+1} = 2p_n \,</math>
3. π is approximated with <math>a_n</math>, <math>b_n</math> and <math>t_n</math> as:
- <math>\pi \approx \frac{(a_n+b_n)^2}{4t_n} \,</math>
The algorithm has second-order convergent nature, which essentially means that the number of correct digits doubles with each step of the algorithm.