The Gauss-Legendre (Brent-Salamin) AGM algorithm for $\pi$

Gauss-Legendre / Brent-Salamin algorithm. Set

$a_0 = 1, \qquad b_0 = \tfrac{1}{\sqrt{2}}, \qquad t_0 = \tfrac{1}{4}, \qquad p_0 = 1,$

and iterate

$a_{n+1} = \frac{a_n + b_n}{2}, \quad b_{n+1} = \sqrt{a_n b_n}, \quad t_{n+1} = t_n - p_n (a_n - a_{n+1})^2, \quad p_{n+1} = 2 p_n.$

Then

$\frac{(a_{n+1} + b_{n+1})^2}{4 t_{n+1}} \longrightarrow \pi,$

and the convergence is quadratic: the number of correct digits roughly doubles at each step, so about $25$ iterations already give tens of millions of digits.

Status: settled, but outside this library's stack. Brent and Salamin published the algorithm independently in 1976, and its correctness is a theorem. It is not open. It is also not reachable here: the proof rests on Gauss's arithmetic-geometric mean and its identification with a complete elliptic integral of the first kind, on the companion integral of the second kind, and on Legendre's relation

$E(k)K(k') + E(k')K(k) - K(k)K(k') = \frac{\pi}{2},$

none of which this library develops.

Not proved in this library. The algorithm is recorded, not derived, and no page here may present it as established.

What is known, and what would prove it here. Everything about it is known; the only obstacle is prerequisite. What would discharge this item is an elliptic integral track: the AGM iteration and its quadratic convergence, the identity $M(1,k') = \pi / (2K(k))$ expressing the AGM through the complete elliptic integral $K$, the second complete integral $E$, and Legendre's relation. That is a substantial classical development in its own right, and it belongs to a page this library does not yet have.

Why it matters here. This library defines $\pi$ analytically and will prove the elementary series and product formulas for it, including the Leibniz series and the Machin-type arctangent formulas. None of those converges as fast as the AGM iteration, and they do not even all converge at the same rate as each other. The Machin-type arctangent series converge linearly: the error falls by a fixed factor per term, so each further digit costs a bounded number of extra terms. The Leibniz series is worse than linear, and it is worth being exact about how much: its partial sums have error of order $1/n$, so each further decimal digit multiplies the number of terms by about ten and a hundred digits are already out of reach. The AGM algorithm converges quadratically, doubling the number of correct digits per step, and it is the reason the record computations of the 1980s and 1990s were feasible at all. Recording it prevents the $\pi$ pages from leaving the impression that the formulas they can prove are the ones that are actually used.