title: Algoritmo di Gauss-Legendre
text: # 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. È 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.
  
  * Valori iniziali:
  
      $a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1.$
  * 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}.$
  * π è 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.
  
  