Salamin-Brent algorithm

The Salamin-Brent algorithm is an algorithm to calculate π that was independently discovered in 1976 by Eugene Salamin and Richard Brent; it is based on the arithmetic-geometric mean.

It works as follows:

• Start out by setting

  $a_{0}=1$

  $b_{0}={\frac {1}{\sqrt {2}}}$

  $s_{0}={\frac {1}{2}}$

• Then iterate

  $a_{k}={\frac {a_{k-1}+b_{k-1}}{2}}$

  $b_{k}={\sqrt {a_{k-1}b_{k-1}}}$

  $s_{k}=s_{k-1}-2^{k}(a_{k}^{2}-b_{k}^{2})$

  $p_{k}={\frac {2a_{k}^{2}}{s_{k}}}$

Then p_k converges quadratically against π; that is, each iteration approximately doubles the number of correct digits.