Algoritmo di Gauss-Legendre

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.

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 206 158 430 000 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 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad t_0 = \frac{1}{4}\qquad 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.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica