Como determino se meu cálculo de pi é preciso?

Eu estava tentando vários métodos para implementar um programa que fornece os dígitos de pi sequencialmente. Eu tentei o método da série Taylor , mas provou convergir extremamente lentamente (quando comparei meu resultado com os valores online depois de algum tempo). Enfim, estou tentando melhores algoritmos.

Assim, ao escrever o programa, fiquei com um problema, como em todos os algoritmos: como sei que os ndígitos que calculei são precisos?

Como sou o atual recordista mundial de mais dígitos de pi, adicionarei meus dois centavos :

A menos que você esteja realmente estabelecendo um novo recorde mundial, a prática comum é apenas verificar os dígitos computados em relação aos valores conhecidos. Então, isso é bastante simples.

Na verdade, tenho uma página da Web que lista trechos de dígitos com o objetivo de verificar cálculos em relação a eles: http://www.numberworld.org/digits/Pi/

Mas quando você entra em um território recorde mundial, não há nada para comparar.

Historicamente, a abordagem padrão para verificar se os dígitos computados estão corretos é recalcular os dígitos usando um segundo algoritmo. Portanto, se qualquer cálculo der errado, os dígitos no final não corresponderão.

Isso normalmente mais que o dobro da quantidade de tempo necessária (já que o segundo algoritmo é geralmente mais lento). Mas é a única maneira de verificar os dígitos calculados depois de entrar no território desconhecido de dígitos nunca antes calculados e em um novo recorde mundial.

Nos dias em que os supercomputadores estavam estabelecendo os registros, dois algoritmos AGM diferentes eram comumente usados:

• Algoritmo de Gauss – Legendre
• Algoritmo de Borwein

Esses dois O(N log(N)^2)algoritmos eram bastante fáceis de implementar.

No entanto, hoje em dia as coisas são um pouco diferentes. Nos últimos três recordes mundiais, em vez de realizar dois cálculos, realizamos apenas um cálculo usando a fórmula mais rápida conhecida ( Fórmula de Chudnovsky ):

Esse algoritmo é muito mais difícil de implementar, mas é muito mais rápido que os algoritmos AGM.

Em seguida, verificamos os dígitos binários usando as fórmulas BBP para extração de dígitos .

Essa fórmula permite calcular dígitos binários arbitrários sem calcular todos os dígitos anteriores. Portanto, é usado para verificar os últimos dígitos binários calculados. Portanto, é muito mais rápido que uma computação completa.

A vantagem disso é:

1. Apenas um cálculo caro é necessário.

A desvantagem é:

1. É necessária uma implementação da fórmula de Bailey – Borwein – Plouffe (BBP).
2. Uma etapa adicional é necessária para verificar a conversão de raiz de binário em decimal.

_{Analisei alguns detalhes de por que verificar os últimos dígitos implica que todos os dígitos estão corretos. Mas é fácil ver isso, pois qualquer erro de computação será propagado para os últimos dígitos.}

Agora, este último passo (verificar a conversão) é realmente bastante importante. Um dos recordistas anteriores realmente nos chamou a atenção nisso, porque, inicialmente, eu não dei uma descrição suficiente de como funcionava.

Então, eu peguei esse trecho do meu blog:

N = # of decimal digits desired
p = 64-bit prime number

Calcule A usando aritmética da base 10 e B usando aritmética binária.

Se A = B, com "probabilidade extremamente alta", a conversão estiver correta.

Para uma leitura mais aprofundada, consulte minha postagem no blog Pi - 5 trilhões de dígitos .

Sem dúvida, para seus propósitos (o que suponho ser apenas um exercício de programação), a melhor coisa é verificar seus resultados com qualquer uma das listagens dos dígitos de pi na web.

E como sabemos que esses valores estão corretos? Bem, eu poderia dizer que existem maneiras da ciência da computação de provar que a implementação de um algoritmo está correta.

Mais pragmaticamente, se pessoas diferentes usam algoritmos diferentes, e todas elas concordam em (escolher um número) mil (um milhão, o que for) casas decimais, isso deve dar a você uma sensação confusa de que eles acertaram.

Historicamente, William Shanks publicou pi com 707 casas decimais em 1873. Pobre rapaz, ele cometeu um erro a partir da 528ª casa decimal.

O mais interessante é que em 1995 foi publicado um algoritmo que possuía a propriedade que calcularia diretamente o enésimo dígito (base 16) de pi sem ter que calcular todos os dígitos anteriores !

Por fim, espero que seu algoritmo inicial não pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...seja o mais simples de programar, mas também é uma das maneiras mais lentas de fazer isso. Confira o artigo pi na Wikipedia para abordagens mais rápidas.

Você pode usar várias abordagens e ver se elas convergem para a mesma resposta. Ou pegue um pouco da rede. O algoritmo de Chudnovsky é geralmente usado como um método muito rápido de calcular pi. http://www.craig-wood.com/nick/articles/pi-chudnovsky/

A série Taylor é uma maneira de aproximar o pi. Como observado, converge lentamente.

Pode-se mostrar que as somas parciais da série Taylor estão dentro de algum multiplicador do próximo termo, longe do valor real de pi.

Outros meios de aproximação de pi têm maneiras semelhantes de calcular o erro máximo.

Sabemos disso porque podemos provar matematicamente.

Você pode tentar computar sin(pi/2)(ou cos(pi/2)nesse caso) usando a série de potências (razoavelmente) convergente rapidamente para sin e cos. (Melhor ainda: use várias fórmulas de duplicação para calcularx=0 para uma convergência mais rápida.)

BTW, melhor do que usar séries para tan(x)é, com a computação, digamos, cos(x)como uma caixa preta (por exemplo, você poderia usar a série taylor como acima) é fazer a busca de raiz via Newton. Certamente existem algoritmos melhores por aí, mas se você não quiser verificar toneladas de dígitos, isso será suficiente (e não é tão complicado de implementar, e você só precisa de um pouco de cálculo para entender por que funciona).