Algoritmo di Gauss-Legendre

Template:F L'algoritmo di Gauss–Legendre è un algoritmo per il calcolo di π. È noto per essere rapidamente convergente, 25 iterazioni producono ben 45 milioni di cifre decimali corrette di π. L'inconveniente è un intensivo uso di memoria.

Il metodo è basato sui lavori di Gauss e Legendre unitamente ai moderni algoritmi per la moltiplicazione e l'estrazione di radice quadrata. Si basa sulla continua sostituzione di due numeri con la loro media aritmetica e geometrica per approssimare la loro media aritmetica-geometrica.

Esempio di algoritmo

La versione presentata qui sotto è anche conosciuta come algoritmo di Brent-Salamin (o Salamin-Brent); è stata scoperta indipendentemente da Richard Brent e Eugene Salamin. È stata usata per calcolare le prime Template:TA cifre decimali di π tra il 18 e il 20 settembre 1999 e il risultato è stato controllato con l'algoritmo di Borwein.

1. Valori iniziali:

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

2. Ripetere le seguenti istruzioni finché la differenza fra $a_n$ e $b_n$ è della precisione voluta:

   $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.$

3. π è approssimato con $a_n$, $b_n$ e $t_n$ come:

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

Le prime tre iterazioni danno:

$3.140...$

$3.14159264...$

$3.14159265358979...$

L'algoritmo ha convergenza del secondo ordine, cioè il numero di cifre corrette raddoppia a ogni passo dell'algoritmo.

Collegamenti esterni

• Template:Collegamenti esterni