Algoritme van Gauss-Legendre

Het algoritme van Gauss-Legendre is een algoritme om de cijfers van het getal pi te berekenen. Het is genoemd naar de wiskundigen Carl Friedrich Gauss en Adrien-Marie Legendre die het theoretisch uitwerkten, maar toen nog geen computers hadden om het toe te passen.

Het is soms ook bekend als algoritme van Brent-Salamin naar Richard Brent en Eugène Salamin die dit in 1975 toepasten. Van 18 tot 20 september 1999 werden hiermee 206 miljard decimalen van pi berekend en het resultaat werd vergeleken met het algoritme van Borwein.

Begin:

$a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1$

Herhaal:

$a_{n+1}={\frac {a_{n}+b_{n}}{2}}$,

$b_{n+1}={\sqrt {a_{n}b_{n}}}$,

$t_{n+1}=t_{n}-p_{n}(a_{n}-a_{n+1})^{2}$,

$p_{n+1}=2p_{n}$.

Einde: π is dan bij benadering:

$\pi \approx {\frac {(a_{n}+b_{n})^{2}}{4t_{n}}}$.

De eerste drie benaderingen leveren:

$3{,}140\dots$

$3{,}14159264\dots$

$3{,}14159265358979\dots$

Het aantal juiste cijfers verdubbelt met elke stap. Het algoritme vraagt wel veel geheugen.