Algoritme de Gauss-Legendre

El algoritme de Gauss-Legendre és un algoritme per a computar els dígits de π.

El método es basa en els treballs individuals de Carl Friedrich Gauss (1777-1855) i Adrien-Marie Legendre (1752-1833) combinats en algoritmes moderns per a la multiplicació i la raïl quadrada. Substituïx repetidament dos números per les seues miges aritmètica i geomètrica, per a obtindre una aproximació a la seua mija aritmètic-geomètrica.

La versió que es presenta ací es coneix també com el algoritme de Brent-Salamin (o Salamin-Brent); que va ser descobert en 1975 i de forma independent per Richard Brent i Eugene Salamin. Es va usar entre el 18 i el 20 de setembre de 1999 per a calcular els primers 206.158.430.000 dígits decimals de π, i el resultat es va comprovar usant l'algoritme de Borwein.

Algoritme

1. Establiment del valor inicial:

$a_0=1b_0=\frac{1}{\sqrt{2}}{t}_0=\frac{1}{4}{p}_0=1$

2. Repetir les següents instruccions fins que la diferència entre $a_n$ i $b_n$ es trobe dins de la precisió desijada:

$x_{n+1}=\frac{a_n+b_n}{2}$

$y_{n+1}=\sqrt{a_n{b}_n}$

$t_{n+1}=t_n-p_n(a_n-x_{n+1}{)}^2$

$a_{n+1}=x_{n+1}$

$b_{n+1}=y_{n+1}$

$p_{n+1}=2p_n$

3. π s'aproxima usant $a_n$, $b_n$ i $t_n$ com:

$\pi \approx \frac{(a_n+b_n{)}^2}{4t_n}$

Les primeres tres iteraciones donen:

$\mathrm{3.140...}$

$\mathrm{3.14159264...}$

$\mathrm{3.14159265358979...}$

L'algoritme té naturalea convergent de segon orde, que essencialment significa que el número de dígits correctes es duplica en cada pas de l'algoritme.

Vore també

• Algoritme de Borwein
• Fòrmula de Bailey-Borwein-Plouffe