algorithm - quien - numero pi completo
¿Cómo puedo determinar si mi cálculo de pi es exacto? (5)
Estaba probando varios métodos para implementar un programa que da los dígitos de pi secuencialmente. Probé el método de la serie de Taylor , pero resultó que convergía extremadamente lentamente (cuando comparé mi resultado con los valores en línea después de algún tiempo) De todos modos, estoy probando mejores algoritmos.
Entonces, mientras escribía el programa, me quedé atascado en un problema, como con todos los algoritmos: ¿Cómo sé que los n dígitos que he calculado son exactos?
La serie de Taylor es una forma de aproximarse a pi. Como se ha señalado, converge lentamente.
Se puede demostrar que las sumas parciales de la serie de Taylor están dentro de algún multiplicador del siguiente término, lejos del valor verdadero de pi.
Otros medios de aproximación de pi tienen formas similares de calcular el error máximo.
Sabemos esto porque podemos probarlo matemáticamente.
Podría intentar calcular sin(pi/2) (o cos(pi/2) para el caso) utilizando la serie de potencias (bastante) rápidamente convergentes para sin y cos. (Aún mejor: use varias fórmulas de duplicación para calcular una x=0 más cercana para una convergencia más rápida).
Por cierto, es mejor que usar series para tan(x) , con computación que dice cos(x) como una caja negra (por ejemplo, podría usar series de taylor como anteriormente) es hacer la búsqueda de raíces a través de Newton. Ciertamente hay mejores algoritmos, pero si no quieres verificar toneladas de dígitos, esto debería ser suficiente (y no es tan difícil de implementar, y solo necesitas un poco de cálculo para entender por qué funciona).
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/
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 maneras de demostrar que la implementación de un algoritmo es correcta.
Más pragmáticamente, si diferentes personas usan diferentes algoritmos, y todos acuerdan (elegir un número) mil (millones, lo que sea) lugares decimales, eso debería darle una sensación borrosa de que lo hicieron bien.
Históricamente, William Shanks publicó pi con 707 lugares decimales en 1873. Pobre hombre, cometió un error al comenzar con el 528 lugar 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 sea pi/4 = 1 - 1/3 + 1/5 - 1/7 + ... Puede que sea el más sencillo de programar, pero también es una de las formas más lentas de hacerlo. . Echa un vistazo a el artículo pi en Wikipedia para enfoques más rápidos.
Ya que soy el poseedor del récord mundial actual para la mayoría de los dígitos de pi, agregaré mis dos centavos :
A menos que esté configurando un nuevo récord mundial, la práctica común es verificar los dígitos calculados con los valores conocidos. Así que 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 llegas al 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 volver a calcular los dígitos utilizando 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 necesario (ya que el segundo algoritmo suele ser más lento). Pero es la única forma de verificar los dígitos calculados una vez que se haya desplazado por el territorio inexplorado de dígitos nunca antes computados y un nuevo récord mundial.
En los días en que los supercomputadores establecían los registros, comúnmente se utilizaban dos algoritmos de gestión de accesos comunes diferentes:
Estos son ambos algoritmos O(N log(N)^2) 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 de 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 utilizando 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:
- Sólo se necesita un cálculo costoso.
La desventaja es:
- Se necesita una implementación de la fórmula de Bailey – Borwein – Plouffe (BBP).
- 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é la verificación de los últimos dígitos implica que todos los dígitos son correctos. Pero es fácil de 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 en realidad bastante importante. Uno de los poseedores del récord mundial en realidad nos llamó a esto porque, inicialmente, no proporcioné una descripción suficiente de cómo funcionó.
Así que he sacado 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 más información, consulte la publicación de mi blog Pi - 5 Trillion Digits .