Calculando pi com Monte Carlo

Trago aqui um algoritmo simples, embora não muito eficiente, para calcular pi. Para isso vamos utilizar um procedimento estatístico conhecido como método de Monte Carlo. O que diabos estatística tem a ver com pi? Descubra em instantes!

Antes de tudo: o que é pi?

Primeiro precisamos dar uma definição a essa constante matemática tão famosa conhecida como pi, ou mais formalmente π. O pi representa a razão entre o comprimento de uma circunferência e seu diâmetro, ou seja:

Onde C é o comprimento, d o diâmetro e r o raio da circunferência. O pi tem muita importância na ciência e engenharia, mas também desperta bastante curiosidade e disputas ao redor do globo. Sempre tem alguém querendo descobrir novas casas decimais, de modo que já foi calculado o valor de pi com 5 trilhões de casas decimais por Shigeru Kondo e Alexander Yee.

O método de Monte Carlo

Quando falamos no método de Monte Carlo, estamos nos referindo a uma série de procedimentos estatísticos baseados em amostras aleatórias de dados. Embora possam haver peculiaridades dependendo da aplicação, podemos identificar 4 passos básicos:

1 - Definir um domínio de entradas possíveis;
2 - Gerar entradas aleatórias distribuídas sobre o domínio;
3 - Realizar cálculos determinísticos com as entradas;
4 - Agregar os resultados.

Vamos botar a mão na massa e entender como funciona na prática.

O algoritmo

Vamos imaginar, por conveniência, um círculo de raio 1 inscrito em um quadrado de raio 2. Assim, vale a razão

Sendo o raio 1, vemos que

Ou seja, precisamos descobrir qual é a fração da área do círculo em relação à área total do quadrado e multiplicar esse valor por 4. Como fazemos isso? Aí entra o método de Monte Carlo: entramos com um número n de pontos aleatórios, de modo que n esteja contido no quadrado, e para cada ponto verificamos se ele está contido no círculo. Basta então dividir o número de pontos dentro do círculo por n, que é o total de pontos gerados. Ilustrando:

Clique para ver a animação. PI 30K, por CaitlinJo (CC-by 3.0).

Precisamos de 2 coisas então: um gerador de valores aleatórios reais no intervalo [0, 2] e verificar se um ponto está contido no círculo. Vamos supor que tal gerador já exista. Concorda que um ponto está contido em uma circunferência de raio 1 se a distância dele até o centro não ultrapassar 1? A geometria analítica nos diz que a distância entre dois pontos (x, y) e (x0, y0) é dada por

Considerando um sistema de coordenadas x-y referente ao quadrado, no qual a origem coincide com o vértice inferior esquerdo do quadrado, vemos que o centro do círculo está localizado no ponto (1, 1). Como a distância não deve ultrapassar 1, finalmente temos

Para quaisquer pontos (x, y) gerados aleatoriamente. Vamos ver uma implementação em C para fixar os conceitos.

Implementando na linguagem C

Aí vai um programinha em C implementando o algoritmo mostrado acima. Note que o método main() supõe a existência de um método drand(double min, double max), que gera um número do tipo double aleatório. Como não é esse o escopo do post, vou deixar tal método por sua conta.

main() {
       int i, pontosCirculo = 0, amostras = 5000000;
       double px, py;
       
       /* Para cada amostra, criar um ponto em (px, py) dentro do quadrado e
       verificar se está dentro do círculo.*/
       for(i = 0; i < amostras; i++) {
                         px = drand(0.0, 2.0);
                         py = drand(0.0, 2.0);
                         
                         /* Verificar se a distância do ponto ao centro do círculo
                         é menor ou igual a 1. Em caso afirmativo, o ponto pertence 
                         ao círculo.*/
                         if(sqrt( pow(px - 1, 2) + pow(py - 1, 2) ) <= 1)
                                    pontosCirculo++;
       }
       
       /* PI = 4 * Área_círculo/Área_quadrado => Área_círculo/Área_quadrado = 
       Pontos_no_círculo/Total_de_pontos. */
       printf("PI = %lf\n", 4.0 * (double)pontosCirculo/amostras);
}

Outros algoritmos

É claro que há muitas outras maneiras mais eficientes, porém não tão simples, de calcular pi. Se estiver interessado no assunto, sugiro a leitura deste artigo da Wikipédia.

Fontes

Monte Carlo method
Monte Carlo Pi