Algoritme van Gauss-Legendre

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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...\!
3.14159264...\!
3.14159265358979...\!

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