Precisión de trabajo requerida para el algoritmo BBP?

Question

Estoy buscando para calcular el n º dígito de Pi en un entorno de memoria baja. Como no tengo decimales disponibles, este integer-only BBP algorithm in Python ha sido un excelente punto de partida. Solo necesito calcular un dígito de Pi a la vez. ¿Cómo puedo determinar el valor más bajo que puedo establecer D, el "número de dígitos de precisión de trabajo"?

D = 4 me da muchos dígitos correctos, pero algunos dígitos estarán desactivados en uno. Por ejemplo, calcular el dígito 393 con precisión de 4 me da 0xafda, de donde extraigo el dígito 0xa. Sin embargo, el dígito correcto es 0xb.

No importa qué tan alto establezca D, parece que al probar un número suficiente de dígitos se encuentra uno en el que la fórmula devuelve un valor incorrecto.

He intentado aumentar la precisión cuando el dígito está "cerca" de otro, p. Ej. 0x3fff o 0x1000, pero no se puede encontrar una buena definición de "cerrar"; por ejemplo, el cálculo en el dígito 9798 me da 0x c de6, que no está muy cerca de 0xd000, pero el dígito correcto es 0xd.

¿Alguien me puede ayudar a calcular cuánta precisión de trabajo se necesita para calcular un dígito dado usando este algoritmo?

Gracias,

edición
Para Referencia:

 
precision (D) first wrong digit 
------------- ------------------ 
3    27 
4    161 
5    733 
6    4329 
7    21139 
8+    ??? 

en cuenta que estoy calculando un dígito a la vez, por ejemplo:

for i in range(1,n): 
    D = 3 # or whatever precision I'm testing 
    digit = pi(i) # extracts most significant digit from integer-only BBP result 
    if(digit != HARDCODED_PI[i]): 
     print("non matching digit #%d, got %x instead of %x" % (i,digit,HARDCODED_PI[i])) 

Answer 1

n importa cuán alto configuro D, parece que probando un número suficiente de dígitos encuentra uno donde la fórmula devuelve un valor incorrecto.

Siempre obtendrá un error si está probando una cantidad suficiente de dígitos: el algoritmo no usa precisión arbitraria, por lo que los errores de redondeo aparecerán eventualmente.

La iteración ilimitada con interrupción cuando el dígito no cambia será difícil de determinar la precisión mínima requerida para un número dado de dígitos.

Lo mejor es determinarlo empíricamente, idealmente comparando con una fuente correcta conocida e incrementando la precisión de los dígitos hasta obtener una coincidencia, o si la fuente correcta no está disponible, comience con su precisión máxima (que Supongo que es 14, ya que el 15º dígito casi siempre contiene un error de redondeo.)

EDITAR: Para ser más precisos, el algoritmo incluye un bucle - desde 0..n, donde n es el dígito que se debe calcular. Cada iteración del ciclo introducirá una cierta cantidad de error. Después de repetir un número suficiente de veces, el error invadirá el dígito más significativo que está computando, y el resultado será incorrecto.

El artículo de la wikipedia usa 14 dígitos de precisión, y esto es suficiente para calcular correctamente el 10 ** 8 dígito. Como has demostrado, menos dígitos de precisión conducen a errores que ocurren antes, ya que hay menos precisión y el error se vuelve visible con menos iteraciones.El resultado neto es que el valor de n para el cual podemos calcular correctamente un dígito se vuelve más bajo con menos dígitos de precisión.

Si tiene D dígitos hexadecimales de precisión, eso es D * 4 bits. Con cada iteración, se introduce un error de 0.5bits en el bit menos significativo, por lo que con 2 iteraciones existe la posibilidad de que el LSB esté equivocado. Durante la suma, estos errores se agregan, y así se acumulan. Si el número de errores sumados alcanza el LSB en el dígito más significativo, entonces el único dígito que extrae será incorrecto. En general, es cuando N> 2 ** (D-0.75). (Correcto a alguna base logarítmica)

Empíricamente extrapolando sus datos, parece que un ajuste aproximado es N = ~ (2 ** (2.05 * D)), aunque hay pocos puntos de datos por lo que puede no ser un predictor preciso .

El algoritmo BBP que ha elegido es iterativo, por lo que se tardará más tiempo en calcular dígitos en la secuencia. Para calcular los dígitos 0..n, tomará O(n^2) pasos.

El artículo de la wikipedia ofrece una fórmula para calcular el n-ésimo dígito que no requiere iteración, solo la exponenciación y los números racionales. Esto no sufrirá la misma pérdida de precisión que el algoritmo iterativo y puede calcular cualquier dígito de pi según sea necesario en tiempo constante (o en el peor tipo logarítmico, dependiendo de la implementación de la exponenciación con el módulo), por lo que calcular n dígitos tomará O(n) tiempo posiblemente O (n log n).