Gauss-Legendre algorithmThe Gauss-Legendre algorithm is an algorithm to compute the digits of Pi.
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 Pi on September 18 to 20, 1999, and the results were checked with Borwein's algorithm.
1. Initial value setting;
- a = 1, b = 1 / √22, t = 1/4, p = 1
- x = (a+b) / 2
- y = √(a*b)
- t = t - p * (a-x)2
- a = x
- b = y
- p = 2 * p
- Pi ≈ (a+b)2 / (4*t)