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

772

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?

Ishan Sharma
fonte
20
mais um problema matemático. bons algoritmos também fornecem uma estimativa do erro.
exemplo
35
Compare contra pi?
Dave Newton
55
@chris: "Literalmente em todo lugar"?
Lightness Races in Orbit
32
Posso verificar até 3.141592653589793238462643383279502; além disso, por que você precisa de um número tão grande de dígitos? (Isso é algo parecido com precisão nível atômico com um círculo o tamanho do universo.)
AJ Henderson
65
Por que você não apenas divide por pi e verifica se o resultado é 1? (brincadeira apenas)
user541686

Respostas:

1629

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:

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 ):

Digite a descrição da imagem aqui

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 .

Digite a descrição da imagem aqui

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

Digite a descrição da imagem aqui

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

Digite a descrição da imagem aqui

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 .

Mysticial
fonte
15
E para responder à outra pergunta sobre como saber quando um algoritmo específico convergiu para N dígitos: Isso requer que você conheça o comportamento de convergência do algoritmo. A série Taylor de ArcTan(1)é logaritmicamente convergente. Portanto, você precisaria de um número exponencialmente grande de termos para convergir - em suma, não o use.
Mysticial
21
Sim, a fórmula de Chudnovsky converge em constantes 14,18 dígitos por termo. Assim, você pode dividir o número total de dígitos por esse para obter quantos termos você precisa. (Valor exato é: Log(151931373056000)/Log(10) = 14.181647462725477655...)
Mysticial
7
@ erikb85 Kinda. A fórmula BBP (até certo ponto) conta como um segundo algoritmo. Mas, por si só, não é suficiente, pois não verifica a conversão na base 10. A idéia de usar a verificação de conversão BBP + para eliminar a necessidade de um segundo cálculo não era minha. Foi feito pela primeira vez por Fabrice Bellard em seu recorde mundial de 2009. Foi uma ideia tão boa que fizemos o mesmo e melhoramos.
Mysticial
83
@FunsukWangadu Eu só posso falar por mim, mas aqui vai: eu nunca me importei com o próprio Pi. Para mim, é apenas outro número. O valor não está no número em si ou nos 10 terabytes de dígitos inúteis, são os métodos usados ​​para alcançá-lo. Os séculos de matemática e as décadas de pesquisa em computação / programação que contribuíram para esse feito são aplicáveis ​​a muitos outros campos e, portanto, são MUITO mais valiosos do que um disco rígido de dígitos. Simplificando: calcular os dígitos do Pi é mais um esporte.
Mysticial
8
@Mystical, apenas tropeçou no seu site de cálculo Pi a partir de outra pergunta sobre o stackoverflow e não pude deixar de ficar boquiaberta e rindo do que vocês fizeram. Amei o disco rígido falhas / terremotos nos logs :) puro incrível!
31413 Joe
48

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.

Larry Smith
fonte
7
Essa última fórmula (fórmula de Leibniz, iirc) realmente alterna adição e subtração.
Thomas
21

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/

argentage
fonte
Reduz as chances, mas ainda não posso ter certeza com a solução de abordagem múltipla, e se ambas estiverem erradas. Verificar na rede não mantém validade, então por que não tirar valores da própria rede. Estou pensando em bbp qual é o mais adequado?
Ishan Sharma
7
@IshanSharma Se os dois algoritmos forem independentes, as chances de ambos os cálculos estarem errados com resultados idênticos são praticamente nulas. Se algo der errado em qualquer computação, os resultados finais não corresponderão - então você sabe que pelo menos um deles está errado.
Mysticial
15

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.

Yakk - Adam Nevraumont
fonte
Destacado. Eu acho que a maioria das respostas aqui simplesmente não está colocando peso suficiente no conceito de prova matemática . Qualquer que seja o seu programa para calcular dígitos de pi, nunca será mais convincente do que a prova matemática mais convincente de que o método do seu programa realmente calcula pi. O que sugere uma restrição diferente em programas que pi calculam pi: que eles devem buscar tanto a compreensão quanto o desempenho e a correção.
Luis Casillas
5

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).

user1974703
fonte
6
Não vejo bem como isso ajudaria a perceber que o milésimo dígito está 1 em 1. Você precisaria de valores muito precisos sin(pi/2), não precisaria?
Matthieu M.
Não sei o que dizer sobre a resposta anterior, a menos que seja uma piada ou algo assim. sin (pi / 2) = 1 cos (pi / 2) = 0 Então, eu diria que aqueles com certeza convergem rapidamente.
BentFranklin
15
Acho que não é óbvio para todos que avaliar sin(x)e cos(x)alta precisão é de fato muito mais difícil do que computar o próprio Pi.
Mysticial
2
Por razões óbvias, você não deve usar sin (pi / 2) para isso. Melhor usar o pecado (pi / 6) e garantir que ele saia exatamente como 1/2.
Robert Lozyniak