Algoritmo di Gauss-Legendre

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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

Note[modifica | modifica wikitesto]

  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.
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica