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.

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^[1]. È 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:

   ${\displaystyle 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 ${\displaystyle a_{n}}$ e ${\displaystyle b_{n}}$ è della precisione voluta:

   ${\displaystyle a_{n+1}={\frac {a_{n}+b_{n}}{2}}}$,

   ${\displaystyle b_{n+1}={\sqrt {a_{n}b_{n}}},}$

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

   ${\displaystyle p_{n+1}=2p_{n}.}$

3. π è approssimato con ${\displaystyle a_{n}}$, ${\displaystyle b_{n}}$ e ${\displaystyle t_{n}}$ come:

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

Le prime tre iterazioni danno:

${\displaystyle 3.140...}$

${\displaystyle 3.14159264...}$

${\displaystyle 3.14159265358979...}$

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

Note

1. Richard P. Brent, Old and new algorithms for pi, in Notices of the AMS, vol. 60, n. 1, American Mathematical Society, gennaio 2013, p. 7, arΧiv:1303.2762.

Collegamenti esterni

• (EN) Eric W. Weisstein, Pi Formulas, su MathWorld, Wolfram Research.

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