Algoritmo de Gauss-Legendre iterativo para o cálculo de pi

O objetivo desta postagem é apresentar a implementação iterativa do algoritmo de Gauss-Legendre em Java e em C para calcular o valor da constante pi (π).

Na postagem Cálculo de Pi via Algoritmo de Gauss-Legendre (Java e C), eu apresentei uma versão recursiva do algoritmo, que é muito lenta e ineficiente.

A versão iterativa desta postagem consome menos memória e é mais rápida.

Independente da versão, a convergência do algoritmo é bem rápida. A seguir, mostro aproximações de pi calculados pelo algoritmo e quantas iterações foram necessárias para atingir cada aproximação

• i = 1: 3,140579250522169
• i = 2: 3,141592646213543
• i = 3: 3,141592653589794
• i = 4: 3,141592653589794
• i = 5: 3,141592653589794

Observe que a convergência foi alcançada na terceira iteração. É claro, nos exemplos utilizei apenas 15 casas decimais. Quanto mais casas precisarmos, mais iterações serão necessárias para alcançar a convergência.

Códigos

A seguir, apresento a implementação do algoritmo em Java e em C.

Código em Java

//GitHub: HenriqueIni
public class GaussLegendre {
    //Calcula numericamente o valor de PI
    public static double pi(int iterations){
        //inicializações
        double a = 1;
        double b = Math.sqrt(2)/2;
        double t = 0.25;
        double p = 1;        
        double a_next, b_next, t_next, aux; //constantes auxiliares
        
        for(int i = 0; i < iterations; i++){
            //cacula as constantes da iteração i
            a_next = (a + b)/2;
            b_next = Math.sqrt(a * b);
            aux = a - a_next; //evita o uso de pow(a, 2)
            t_next = t - p * aux * aux;
            
            //atualização das variáveis
            p = 2 * p;
            a = a_next;
            b = b_next;
            t = t_next;
        }
        aux = (a + b)/2; //evita o uso de pow(a, 2)
        return aux * aux / t;
    }
    //Testes
    public static void main(String[] args) {
        for(int i = 0; i <= 5; i++){
            System.out.printf("i = %d: %1.15f\n", i, pi(i));
        }
    }
}
            

Código em C

            
//GitHub: HenriqueIni
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//Calcula numericamente o valor de PI
double pi(int iterations){
    //inicializações
    double a = 1;
    double b = sqrt(2)/2;
    double t = 0.25;
    double p = 1;
    double a_next, b_next, t_next, aux; //constantes auxiliares
    
    int i;    
    for(i = 0; i < iterations; i++){
        //cacula as constantes da iteração i
        a_next = (a + b)/2;
        b_next = sqrt(a * b);
        aux = a - a_next; //evita o uso de pow(a, 2)
        t_next = t - p * aux * aux;
        
        //atualização das variáveis
        p = 2 * p;
        a = a_next;
        b = b_next;
        t = t_next;
    }
    aux = (a + b)/2; //evita o uso de pow(a, 2)
    return aux * aux / t;
}
int main() {
    int i;
    for(i = 0; i <= 5; i++){
        printf("i = %d: %1.15f\n", i, pi(i));
    }
    return 0;
}
            

Curiosidade

Em 2002, o Professor Yasumasa Kanada, da Universidade de Tóquio, quebrou o recorde mundial no número de casas decimais de pi calculadas. Kanada calculou o valor de pi com precisão de 1,2411 trilhão de casas decimais [1].

Nos cálculos, ele utilizou o algoritmo de Gauss-Legendre [1]. Posteriormente, em 2009, esse recorde foi superado.

Referências

[1] Everything 2: Yasumasa Kanada. Acesso em 12 de abril de 2018.