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 (†1855) en Adrien-Marie Legendre (†1833) die het theoretisch uitwerkten, maar toen nog geen rekenautomaat 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 Plouffe (1995) en Bailey, Borwein (1997).

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}}}$,

Het rekenkundig en geometrisch gemiddelde gekoppeld.

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

waarin $p_{n+1}=2p_{n}=2^{n+1}$, $t_{n+1}-t_{n}=-p_{n}(a_{n}-b_{n})^{2}/4$.

Einde: π wordt dan benaderd met

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

De eerste drie benaderingen (${\textstyle n=0}$: ${\textstyle 1{\frac {1}{2}}+{\sqrt {2}}=2,91}$) leveren:

$3{,}140\dots$

$3{,}14159264\dots$

$3{,}14159265358979\dots$

Het aantal juiste cijfers in π verdubbelt met elke stap.

Het algoritme vraagt veel geheugenruimte voor precieze a,b,t-waarden hetzij (noot 4) optellingen, delingen en worteltrekking.

Bronnen, noten en/of referenties