Pi veces e (o Pie si te gusta la notación ambigua) a 100 decimales es:
8.5397342226735670654635508695465744950348885357651149618796011301792286111573308075725638697104739439...
( OIES A019609 ) ( argumento para una posible irracionalidad )
Su tarea es escribir un programa que tome un número entero positivo N y produzca Pi * e truncado a N decimales. por ejemplo, si N = 2, entonces la salida debería ser 8.53
.
Este es un problema de optimización, por lo que ganará el envío que puede proporcionar la salida correcta para el valor más alto de N.
Para garantizar que todas las presentaciones se juzguen utilizando la misma potencia informática, su código debe ejecutarse en ideone , utilizando cualquier lenguaje que admitan. De acuerdo con las preguntas frecuentes de ideone , hay un límite de tiempo de ejecución de 5 segundos para los usuarios que no han iniciado sesión. Este límite de 5 segundos es el que debe usar, no el límite de 15 segundos para los usuarios registrados. (Consulte las preguntas frecuentes para conocer otros límites, como la memoria, el tamaño del código, etc.)
Específicamente, cualquier persona que no haya iniciado sesión en ideone debería poder ejecutar su programa en ideone para todos los valores de N desde 1 hasta un máximo de Nmax, y ver la salida correcta casi todo el tiempo . sin ninguna Time limit exceeded
o Memory limit exceeded
, etc. errores. La presentación con el mayor Nmax gana.
(No importa si el tiempo real que se tarda es una pizca de más de 5 segundos, siempre y cuando ideone no dé errores. " Casi todo el tiempo " se define como más del 95% del tiempo para cualquier N. en particular)
Detalles
- Puede usar cualquier método matemático que desee para calcular Pi * e, pero no puede codificar la salida más allá de la primera docena de dígitos de Pi, e o Pi * e .
- Su programa debería poder funcionar para cualquier N, dados los recursos ilimitados.
- Puede usar constantes Pi o e integradas si su idioma las tiene.
- No puede acceder a sitios web o recursos externos a su código (si ideone lo permite).
- Más allá de la codificación y el acceso a recursos externos, cualquier cosa que ideone permita es casi seguro que está bien.
- Su entrada y salida debe (obviamente) funcionar con lo que ideone proporciona para E / S (stdin / stdout solo parece). Está bien si necesita comillas alrededor de la entrada N o la salida es algo así
ans = ...
, etc. - Incluya un enlace a un fragmento de ideone de su código con su Nmax como entrada.
- Si sucede que hay un empate (solo es probable si las presentaciones múltiples alcanzan el límite de caracteres de salida de 64kB), la respuesta de votos más alta gana.
fuente
Respuestas:
Python - 65535
http://ideone.com/knKRhn
Ideone no parece haberse
gmpy2
instalado, lo cual es lamentable por al menos dos razones. Uno, porque haría el cálculo mucho más rápido, y dos, porque hace que cualquier fórmula que requiera una raíz cuadrada de precisión arbitraria sea poco práctica.La fórmula que uso para π fue listada por Ramanujan como Fórmula (39):
que converge a una tasa de ~ 5.89 dígitos por término. Que yo sepa, esta es la serie convergente más rápida de su tipo que no requiere la evaluación de una raíz cuadrada de precisión arbitraria. La fórmula (44) en el mismo documento (tasa de convergencia ~ 7.98 dígitos por término) se conoce con mayor frecuencia como la fórmula de Ramanujan.
La fórmula que uso para e es la suma de factoriales inversos. El número de términos requeridos se calcula como Γ -1 ( 10 n ), usando una aproximación que encontré en mathoverflow . El componente Lambert W 0 se encuentra utilizando el Método de Newton.
El cálculo de cada una de estas sumas se realiza a través de la evaluación rápida de la función E (más generalmente conocida como división binaria), ideada originalmente por Karatsuba. El método reduce una suma de n términos a un solo valor racional p / q . Estos dos valores se multiplican para producir el resultado final.
Actualización: el
perfil reveló que más de la mitad del tiempo necesario para el cálculo se gastó en la división final. Solo se necesitan los bits más altos de log 2 (10 n ) de q para obtener una precisión completa, por lo que recorto algunos de antemano. El código ahora llena el búfer de salida de Ideone en 3.33s .
Actualización 2:
Dado que este es un desafío de optimización , decidí escribir mi propia rutina de división para combatir la lentitud de CPython. La implementación de lo
divnr
anterior usa la División Newton-Raphson . La idea general es calcular d = 1 / q · 2 n usando el Método de Newton, donde n es el número de bits que requiere el resultado, y calcular el resultado como p · d >> n . El tiempo de ejecución ahora es 2.87s , y esto es sin cortar bits antes del cálculo; No es necesario para este método.fuente
PARI / GP: 33000
Este es básicamente el programa dado en OEIS , modificado para tomar la entrada y formatear la salida correctamente. Debería servir como línea de base para vencer, si nada más.
Yo supongo que esto es exacto. Lo comprobé a 100 y 20k contra OEIS, y coincidió con ambos. Es bastante difícil encontrar más dígitos en línea para verificar.
Para 33,000 toma alrededor de 4.5s, por lo que probablemente podría ser golpeado un poco. Me cansé de jugar con la entrada y el bucle de envío / compilación / ejecución lento de ideone.
Enlace de Ideone.com
fuente
Str(floor(frac(x)*10^m)
, va cientos / miles de veces más rápido.Python 3
Como el construido en pi y e no tiene suficientes dígitos, decidí calcular el mío.
IDEOne enlace
Salida para STDIN = 1000:
fuente
should be able to work for any N, given unlimited resources
regla. La mayor parte de los resultados son ceros en torno a N = 10000.)NameError: name 'xrange' not defined
.Scala - 1790
IDEOne en http://ideone.com/A2CIto .
Usamos la fórmula de Wetherfield para π (y el código de fórmula de Machin toscamente portado desde aquí ). Calculamos e usando la serie de potencia ordinaria.
fuente