¿Cómo determino si mi cálculo de pi es exacto?

Estaba probando varios métodos para implementar un programa que da los dígitos de pi secuencialmente. Probé el método de la serie Taylor , pero resultó converger extremadamente lento (cuando comparé mi resultado con los valores en línea después de algún tiempo). De todos modos, estoy intentando mejores algoritmos.

Entonces, mientras escribía el programa me quedé atrapado en un problema, como con todos los algoritmos: ¿Cómo sé que los ndígitos que he calculado son correctos?

Como soy el actual poseedor del récord mundial de la mayoría de los dígitos de pi, agregaré mis dos centavos :

A menos que esté estableciendo un nuevo récord mundial, la práctica común es verificar los dígitos calculados con los valores conocidos. Entonces eso es bastante simple.

De hecho, tengo una página web que enumera fragmentos de dígitos con el fin de verificar los cálculos en su contra: http://www.numberworld.org/digits/Pi/

Pero cuando entras en territorio de récord mundial, no hay nada con lo que comparar.

Históricamente, el enfoque estándar para verificar que los dígitos calculados son correctos es recalcular los dígitos usando un segundo algoritmo. Entonces, si cualquiera de los cálculos falla, los dígitos al final no coincidirán.

Esto suele hacer más del doble de la cantidad de tiempo necesaria (ya que el segundo algoritmo suele ser más lento). Pero es la única forma de verificar los dígitos calculados una vez que te has adentrado en el territorio desconocido de dígitos nunca antes calculados y un nuevo récord mundial.

En los días en que las supercomputadoras establecían los registros, se usaban comúnmente dos algoritmos AGM diferentes :

• Algoritmo Gauss-Legendre
• Algoritmo de Borwein

Ambos son O(N log(N)^2)algoritmos que fueron bastante fáciles de implementar.

Sin embargo, hoy en día, las cosas son un poco diferentes. En los últimos tres récords mundiales, en lugar de realizar dos cálculos, realizamos solo un cálculo utilizando la fórmula más rápida conocida ( Fórmula Chudnovsky ):

Este algoritmo es mucho más difícil de implementar, pero es mucho más rápido que los algoritmos AGM.

Luego verificamos los dígitos binarios usando las fórmulas BBP para la extracción de dígitos .

Esta fórmula le permite calcular dígitos binarios arbitrarios sin calcular todos los dígitos anteriores. Por lo tanto, se utiliza para verificar los últimos dígitos binarios calculados. Por lo tanto, es mucho más rápido que un cálculo completo.

La ventaja de esto es:

1. Solo se necesita un cálculo costoso.

La desventaja es:

1. Se necesita una implementación de la fórmula Bailey – Borwein – Plouffe (BBP).
2. Se necesita un paso adicional para verificar la conversión de radix de binario a decimal.

_{He pasado por alto algunos detalles de por qué verificar los últimos dígitos implica que todos los dígitos son correctos. Pero es fácil ver esto, ya que cualquier error de cálculo se propagará a los últimos dígitos.}

Ahora este último paso (verificar la conversión) es bastante importante. Uno de los poseedores del récord mundial anterior nos llamó la atención sobre esto porque, inicialmente, no di una descripción suficiente de cómo funcionaba.

Así que saqué este fragmento de mi blog:

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

Calcule A usando aritmética de base 10 y B usando aritmética binaria.

Si A = B, entonces con "probabilidad extremadamente alta", la conversión es correcta.

Para leer más, vea la publicación de mi blog Pi - 5 Trillion Digits .

Sin lugar a dudas, para sus propósitos (que supongo que es solo un ejercicio de programación), lo mejor es verificar sus resultados con cualquiera de los listados de los dígitos de pi en la web.

¿Y cómo sabemos que esos valores son correctos? Bueno, podría decir que hay formas informáticas para demostrar que la implementación de un algoritmo es correcta.

Más pragmáticamente, si diferentes personas usan diferentes algoritmos, y todos están de acuerdo en (elegir un número) mil (millones, lo que sea) lugares decimales, eso debería darle una sensación cálida y difusa de que acertaron.

Históricamente, William Shanks publicó pi con 707 decimales en 1873. Pobre hombre, cometió un error comenzando en el 528º decimal.

Muy interesante, en 1995 se publicó un algoritmo que tenía la propiedad de calcular directamente el enésimo dígito (base 16) de pi sin tener que calcular todos los dígitos anteriores .

Finalmente, espero que su algoritmo inicial no pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...haya sido el más simple de programar, pero también es una de las formas más lentas de hacerlo. Consulte el artículo pi en Wikipedia para obtener enfoques más rápidos.

Podría usar múltiples enfoques y ver si convergen en la misma respuesta. O toma algo de la red. El algoritmo de Chudnovsky se usa generalmente como un método muy rápido para calcular pi. http://www.craig-wood.com/nick/articles/pi-chudnovsky/

La serie Taylor es una forma de aproximar pi. Como se señaló, converge lentamente.

Se puede demostrar que las sumas parciales de la serie Taylor están dentro de algún multiplicador del próximo término lejos del verdadero valor de pi.

Otros medios de aproximación de pi tienen formas similares de calcular el error máximo.

Sabemos esto porque podemos demostrarlo matemáticamente.

Podría intentar calcular sin(pi/2)(o cos(pi/2)para el caso) utilizando la serie de potencia (bastante) convergente rápidamente para sin y cos. (Aún mejor: use varias fórmulas de duplicación para calcular más cercax=0 una convergencia rápida).

Por cierto, mejor que usar series para tan(x)es, con la computación, por ejemplo, cos(x)como un cuadro negro (por ejemplo, podría usar la serie taylor como se indicó anteriormente) es hacer la búsqueda de raíces a través de Newton. Ciertamente, existen mejores algoritmos, pero si no desea verificar toneladas de dígitos, esto debería ser suficiente (y no es tan difícil de implementar, y solo necesita un poco de cálculo para entender por qué funciona).