display | more...

Also known as the Gauss-Legendre algorithm, this algorithm was devised independently by Eugene Salamin and Richard Brent in 1976 as a very fast way to compute pi. Up until that time a laborious arctangent formula was used which had a growth rate of n-squared -- that is, doubling the number of digits you had now took four times as many iterations. The Brent-Salamin algorithm, by contrast, approximately doubles the number of digits with each iteration.

It is entirely based upon the arithmetic-geometric mean formula which was used by Gauss to evaluate elliptic integrals. Since its discovery, other related algorithms for computing pi have been discovered, but none of them have proven to be any faster.

The algorithm works as follows: start with a=1, b=1/sqrt(2), r=1, and s=1/2. Then do these steps:

  1. A = (a+b)/2
  2. B = sqrt(a*b)
  3. C = (A-b)^2
  4. R = 2*r
  5. S = s - C*R
  6. P = 2*A^2/S
  7. If C = 0 to the precision used, stop, and pi = P to that precision
    (For example, if C = 0.00004, then P = pi to four digits.)
  8. Replace a by A, b by B, r by R, and s by S
  9. Go back to step 1

These steps can be easily programmed in whatever programming language you favor and, using step 7 as a break point, will compute pi to as many decimal places as your machine can store. It's even available online in open source for just about every OS you can imagine, under the name "pi_css5". Even with a pocket calculator, it's very fast -- just four iterations of the algorithm will give you pi accurate to twenty digits.