Se requiere de Precisión para el BBP Algoritmo?

Question

Estoy buscando para el cálculo de la nth dígitos de Pi en una memoria baja de medio ambiente.Como no tengo decimales disponible para mí, este entero-sólo BBP algoritmo en Python ha sido un gran punto de partida.Sólo tengo que calcular un dígito de Pi en un momento. ¿Cómo puedo determinar el mínimo que puedo conjunto D, el "número de dígitos de precisión de trabajo"?

D=4 me da muchos correcto de dígitos, pero un par de dígitos será desactivada por uno.Por ejemplo, calcular el dígito 393 con una precisión de 4 me da 0xafda, de la que extraigo el dígito 0xa.Sin embargo, el dígito correcto es 0xb.

No importa lo alto que establece D, parece que las pruebas de un suficiente número de dígitos que se encuentra uno en el que la fórmula devuelve un valor incorrecto.

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

Alguien me puede ayudar a averiguar cuánto trabajo de precisión es necesaria para calcular un determinado dígito usando este algoritmo?

Gracias,

editar
Para La Referencia:

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

Tenga en cuenta que yo soy el cálculo de 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

No importa lo alto que conjunto D, parece que la prueba de un número suficiente de dígitos encuentra un uno donde la fórmula devuelve un valor incorrecto.

Siempre se obtendrá un error si está probando un número suficiente de los dedos -. El algoritmo no utiliza precisión arbitraria, por lo que los errores de redondeo se mostrarán finalmente

La iteración sin límites con el descanso cuando el dígito no cambio va a ser difícil determinar la precisión mínima requerida para un número determinado de dígitos.

Su mejor apuesta es determinar empíricamente, a ser posible mediante la comparación contra una fuente correcta conocida, y aumentar el número de precisión dígitos hasta obtener partido, o si una fuente correcta no está disponible, comience con su precisión máxima (que yo conjetura es 14, ya que el día 15 dígitos casi siempre contendrá un error de redondeo.)

EDIT: Para ser más precisos, el algoritmo incluye un bucle - de 0..n, donde n es el dígito de calcular. Cada iteración del bucle introducirá una cierta cantidad de error. Después looping un número suficiente de veces, el error invadirá el dígito más significativo que se está calculando, por lo que el resultado será un error.

El artículo de Wikipedia utiliza 14 dígitos de precisión, y esto es suficiente para calcular correctamente el dígito 10 ** 8. Como se ha mostrado, un menor número de dígitos de precisión conduce a errores occuring anterior, ya que hay menos precisión y el error se hace visible con un menor número de iteraciones. El resultado neto es que el valor de n para el cual podemos calcular correctamente un dígito se vuelve más baja con un menor número de dígitos de precisión.

Si usted 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 la LSB es un error. Durante la adición, se añaden estos errores, y así se acumulan. Si el número de errores alcance resumió el LSB en el dígito más significativo, entonces el dígito a extraer será incorrecto. En términos generales, es decir, cuando N> 2 ** (D-0.75). (Correcta a alguna base logarítmica.)

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

El algoritmo BBP elegido es iterativo, y por lo que requerirá cada vez más largos a los dígitos de cómputo en la secuencia. Para calcular 0..n dígitos, tomará las medidas necesarias O(n^2).

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