Algoritmo de Gauss-Legendre

O algoritmo de Gauss-Legendre é um algoritmo para calcular os dígitos de π. É notável por ser rapidamente convergente, com 25 iterações produz 45 milhões de dígitos corretos do π. Entretanto, o inconveniente é que usa muita memória e consequentemente não é usado em fórmulas como a Fórmula de Machin.

O método é baseado no trabalho individual de Carl Friedrich Gauss (1779-1815) e Adrien-Marie Legendre (1799-1855) combinado com os algoritmos modernos para multiplicação e raízes quadradas. Substitui repetidamente dois números pela sua média aritmética e pela sua média geométrica, a fim de aproximar a sua média aritmética-geométrica.

1. Valores iniciais: ${\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1.\!}$

2. Repita as seguintes instruções até que a diferença de ${\displaystyle a_{n}\!}$ e ${\displaystyle b_{n}\!}$ esteja na precisão desejada:

${\displaystyle {\begin{aligned}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}.\end{aligned}}}$

3. π é então aproximado como:

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

As 3 primeiras iterações dão (aproximações incluindo o primeiro dígito duvidoso):

${\displaystyle 3.140\dots \!}$

${\displaystyle 3.14159264\dots \!}$

${\displaystyle 3.1415926535897932382\dots \!}$

O algoritmo tem uma natureza convergente de segunda ordem, o que significa que o número de dígitos corretos duplica a cada iteração do algoritmo.

Algoritmo em Java e em C