Iteraciones de Bailey – Borwein – Plouffe
Hemos visto algunos desafíos pi en PPCG, pero ninguno que dicte específicamente el algoritmo que debe usar. Me gustaría ver implementaciones del algoritmo Bailey – Borwein – Plouffe en cualquier idioma hasta la iteración n
. La fórmula es la siguiente:
Su algoritmo debe generar cada iteración hasta n, mostrando sumas intermedias, así como el resultado final para formar un "triángulo". También puede usar la forma polinómica reducida del algoritmo que se muestra en la página de wikipedia. A continuación se muestra un ejemplo de ejecución n=50
:
3
3.1
3.14
3.141
3.1415
3.14159
3.141592
3.1415926
3.14159265
3.141592653
3.1415926535
3.14159265358
3.141592653589
3.1415926535897
3.14159265358979
3.141592653589793
3.1415926535897932
3.14159265358979323
3.141592653589793238
3.1415926535897932384
3.14159265358979323846
3.141592653589793238462
3.1415926535897932384626
3.14159265358979323846264
3.141592653589793238462643
3.1415926535897932384626433
3.14159265358979323846264338
3.141592653589793238462643383
3.1415926535897932384626433832
3.14159265358979323846264338327
3.141592653589793238462643383279
3.1415926535897932384626433832795
3.14159265358979323846264338327950
3.141592653589793238462643383279502
3.1415926535897932384626433832795028
3.14159265358979323846264338327950288
3.141592653589793238462643383279502884
3.1415926535897932384626433832795028841
3.14159265358979323846264338327950288419
3.141592653589793238462643383279502884197
3.1415926535897932384626433832795028841971
3.14159265358979323846264338327950288419716
3.141592653589793238462643383279502884197169
3.1415926535897932384626433832795028841971693
3.14159265358979323846264338327950288419716939
3.141592653589793238462643383279502884197169399
3.1415926535897932384626433832795028841971693993
3.14159265358979323846264338327950288419716939937
3.141592653589793238462643383279502884197169399375
3.1415926535897932384626433832795028841971693993751
3.14159265358979323846264338327950288419716939937510
La precisión de cada iteración debe ser igual a la n
que se pasa al algoritmo, es decir que cada iteración debe calcular pi hasta la pasada n
para todos k
.
Reglas:
- Los elementos integrados no están permitidos, ni tampoco
pi
, debe usar la fórmula. - Debe admitir
n
hasta un máximo que su idioma permita en términos del cálculo de16^n
. Si la entrada está causando un desbordamiento aritmético durante el cálculo después de lasx<n
ejecuciones porque su idioma solo admite decimales hasta2^32-1
, esto está bien. Cualquier otra suposición sobren
no está bien. - Usted DEBE proporcionar una explicación de cómo ha llegado hasta la salida si no es obvio. Por ejemplo, si publica en un idioma de Golf, se requiere un desglose del 100%. Esto es para asegurarse de que está utilizando el algoritmo que se especifica.
- Los agujeros de bucle estándar no están permitidos.
- Este es el código de golf, el conteo de bytes más bajo gana aquí.
Código de referencia (código utilizado para generar el ejemplo):
public static void main(String[] args) {
(0..50).each {
n->
def x=(0..n).collect {
j->
def k=new BigDecimal(j)
def s={it.setScale(n)}
def a=s(1.0g).divide(s(16.0g)**s(k))
def b=s(4.0g)/(s(8.0g)*s(k)+s(1.0g))
def c=s(2.0g)/(s(8.0g)*s(k)+s(4.0g))
def d=s(1.0g)/(s(8.0g)*s(k)+s(5.0g))
def e=s(1.0g)/(s(8.0g)*s(k)+s(6.0g))
def f=a*(b-c-d-e)
}.sum()
println(n + "\t" + x.setScale(n, BigDecimal.ROUND_DOWN))
}
}
Esta implementación se limita a n=255
, puede limitar a menos o más.
Esta implementación se realizó en Groovy.
Calculate foo via x method
desafíos.Respuestas:
05AB1E ,
635250 bytesFórmula de especialización
Pruébalo en línea!
Fórmula BBP
Pruébalo en línea!
fuente
Python 2,
109108bytesPruébalo en Ideone .
fuente
Python 2, 174 bytes
Hombre, este es un momento en el que desearía que Python tuviera una forma más fácil de mantener una precisión infinita para decimales. Posiblemente, implementar su propio tipo de precisión infinita para este desafío es más corto, pero no puedo imaginar cómo. La fórmula está escrita literalmente.
Ejemplo de salida para
n=100
(con algunos números de línea agregados):Esto parece funcionar para números más grandes, se
n=1000
ejecuta en un par de segundos yn=10000
parece que todavía no me ha dado ningún error!fuente
Haskell
101100 bytesGracias a @nimi por un byte.
Implementación directa. Calcula
n
hasta 15 dígitos (doble precisión estándar).fuente
l<-[8*fromIntegral k]
en lugar delet ...
guardar un byte.J,
736462 bytesEsto genera cada aproximación a n dígitos como una cadena formateada. Esto usa la simplificación polinómica de la fórmula y obtiene el primer n dígitos multiplicando la suma por una potencia de 10, poniéndola en el piso y dividiéndola por la misma potencia de 10.
La entrada se toma como un entero extendido, lo que significa que se usan racionales cuando se produce una división que mantiene los resultados exactos.
Uso
Esta es la salida para n = 100, que muestra las sumas acumuladas para k en [0, 100].
Explicación
Primero haga el rango [0, n ], que se muestra para n = 5
Multiplica cada uno por 8
Forme la tabla de suma entre
[1, 4, 5, 6]
y los productos con 8Divide cada fila por
[4, 2, -1, 1]
Luego reduzca las columnas de abajo hacia arriba usando la resta
Divida cada 16 k por k en [0, n ] por cada resultado
Encuentra las sumas acumulativas
Calcule 10 k para k en [0, n ] y multiplíquelo con cada
Luego piso cada uno de los productos
Divídalo por la misma potencia de 10 para obtener los resultados.
fuente
PARI / GP, 86 bytes
O sin el punto decimal en 69 bytes :
En lugar de dividir entre 16 k cada iteración, el valor anterior de p se multiplica por 16 . El piso de p ÷ (8/5) k es entonces el valor de π truncado al número correcto de dígitos.
Uso de muestra
fuente
C GCC, 118 bytes
Golfizado:
Sin golf:
Para cambiar n, simplemente cambie while (k <15) a while (k <n)
salida:
la precisión máxima es de 15 decimales, podría aumentar a cualquier valor con gmp, pero tal vez el próximo día pi: P
con letra bonita, 143 bytes
Golfizado:
Sin golf:
salida:
fuente
Fórmula IBM / Lotus Notes, 125 bytes
Fórmula en un campo calculado con otro campo llamado "a" para entrada.
Básicamente, un puerto del algoritmo de la respuesta de Python de @shebang. Calcula hasta 15 dígitos después de lo cual se trunca debido a una limitación del idioma (ver salida). Tuve que desperdiciar 12 bytes con la instrucción @If al final solo para deshacerme del. después de los 3 al inicio: - /
Sin golf
fuente
C #, 183 bytes
Golfizado:
Sin golf:
fuente
3.14159265358979
para cualquiern >= 14
debido a la doble precisión?APL (NARS), 206 caracteres, 412 bytes
Esto encuentra toda la approssimation en big racional, que usar una función que convierta big racional en cadena numérica ... prueba:
fuente