|
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;
-
2. Repeat the following instructions until the difference of a and b is within the desired accuracy:
-
-
- t = t - p(a - x)2
- a = x
- b = y
- p = 2p
3. π is approximated with a, b and t as:
-
The algorithm has second order convergent nature, which essentially means that the number of correct digits doubles with each
step of the algorithm.
|