El problema es el siguiente.
Entrada: un enteron
Salida: El primo más pequeño más grande que n
.
El desafío es dar el código más rápido posible para hacer esto. Probaré el código en valores que comiencen con un tamaño aproximado 10^8
10^200
y dupliquen el tamaño hasta que tome más de un minuto y 10 segundos en mi computadora.
El código ganador encontrará el próximo primo para el tamaño de entrada más grande.
A modo de comparación, un tamiz simple escrito en python es capaz de encontrar el próximo cebado más grande que 10^8
en unos 20
segundos.
El requisito de que pueda probarlo en mi computadora ubuntu de 4 GB de RAM es estricto. Todo el código debe ser libre (en ambos sentidos) y si usa bibliotecas, también debe ser libre y fácil de instalar. Cualquier primo falso reportado descalificará de inmediato el envío.
También otorgaré elogios por separado para los ganadores en cada lenguaje de programación si el código está completamente escrito en ese idioma sin el uso de bibliotecas externas. También mantendré una tabla de los tiempos más rápidos a medida que avanza la competencia para que las personas puedan ver cómo están.
Tabla hasta ahora
- Pitón. Un
357
número primo asombroso343239883006530485749095039954069660863471765007165270469723172959277159169882802606127982033072727748864815569574042901856099399985832190628701414555752857600000000000000000000000000000000000000002872284792758930912601189043411951050852357613658978971208596097634095500808832510259693761982135208603287199546795000697807728609476163156438356035166156820611
fue el número final en menos de 10 segundos usando el código provisto porprimo
. ¿Alguien superará esta primera entrada?
fuente
fast next prime function
.Respuestas:
Python ~ 451 dígitos
Esto es parte de la biblioteca que escribí para un problema de factorización de semiprime , con funciones innecesarias eliminadas. Utiliza la prueba de primalidad Baillie-PSW , que técnicamente es una prueba probabilística, pero hasta la fecha, no hay pseudoprimos conocidos, e incluso hay una recompensa en efectivo si puede encontrar una (o por proporcionar una prueba de que no existe) .
Editar : no me había dado cuenta de que Python tiene una exponenciación modular incorporada. Reemplazar el mío por los resultados incorporados en un aumento del rendimiento de aproximadamente el 33%.
my_math.py
Un script de prueba de muestra:
Se eligió un factor de 317, porque es aproximadamente la raíz cuadrada de
10000
, agregando aproximadamente 2.5 dígitos por iteración (y porque duplicar era demasiado lento para sentarse). La salida muestra el número actual de dígitos y el tiempo necesario.Resultados de muestra:
Todo el código ahora es compatible con Python 3.
fuente
next_prime((2^520)*(10^200))
unos 15 segundos en mi máquina, así que a primera vista esto es bastante impresionante. Sin embargo ...next_prime((2^520)*(10^200),proof=False)
toma 0.4 segundos porque solo verifica la pseudoprimidad. Su afirmación "no se conocen pseudoprimos" es muy convincente a medida que el número de bits supera los 64. Para 357 dígitos, ni siquiera estoy convencido de forma remota por la falta de contraejemplos.C ++ con GMP: 567 dígitos
Utiliza la implementación de Miller-Rabin en GMP. Puede devolver un falso positivo, pero la buena suerte en realidad golpea a uno con probabilidad 2 ^ -200.
Encuentra el primo
10^200 * 2^1216 + 361
(567 dígitos) antes de correr con el tiempo en mi laptop lenta.fuente
Perl con módulo GMP, 1300 dígitos
Usando mi módulo Math :: Prime :: Util y su back end GMP . El punto de cruce exacto dependerá de su computadora y de si tiene la última biblioteca GMP. Todo el código es gratuito (los módulos están en github y CPAN, y GMP está disponible gratuitamente). Los ejecuté en Ubuntu de AWS, así como en Ubuntu de escritorio (y Fedora, y AIX, y NetBSD, etc.).
El código central está en C y C + GMP. next_prime de MPU ve que el número es demasiado grande y lo reenvía al back-end de GMP (o al código puro de Perl si el back-end no está instalado). Eso stringiifica y convierte a un mpz, y convertirá el resultado nuevamente en el tipo de objeto de entrada o Math :: BigInt. next_prime en sí hace:
La prueba principal probable es:
Todo lo anterior al ES BPSW es solo optimización, que por supuesto queremos para next_prime. next_prime también se implementa en Perl usando el módulo Math :: BigInt (en el núcleo con los extremos opcionales Pari y GMP). Eso hace AES BPSW (como Pari) pero no está tan optimizado.
He pensado en los méritos de una versión basada en tamiz parcial, utilizando un rango de, por ejemplo, 2 méritos. Simplemente no estoy seguro de si esto sería realmente mejor, ya que la mayoría de las veces estaríamos haciendo un tamizado innecesario ya que el espacio es pequeño, y a veces para un espacio grande tendríamos que repetirlo varias veces.
La biblioteca implementa ECPP (incluidos los certificados) para que podamos ejecutar una prueba del resultado, pero 1200 dígitos es realmente demasiado grande para el pequeño conjunto predeterminado de polinomios incluidos (hay un método para descargar conjuntos más grandes; las pruebas tomarían un poco menos de tiempo). 15 minutos, que es un poco más rápido que el APR-CL de Pari pero un poco más lento que el mpz_aprcl de WraithX). Una desventaja de ECPP vs. APR-CL es que tiene más variación de tiempo, por lo que hay una buena posibilidad de que exceda los 10 segundos en algún número antes de que llegue el tiempo promedio. Con una prueba, creo que estamos limitados a algo en el rango de 400 dígitos a menos que permitamos software de subprocesos múltiples.
Decidí probar con la misma secuencia utilizada por primo. Llegó a los 1191 dígitos, ya que es allí donde llegamos a una brecha de 18138. También probé el código de primo usando el último my_math.py. Llega a 630 dígitos con la secuencia 10 ^ e y 641 con su secuencia. Muy impresionante para el código compacto de Python sin muchas pruebas preliminares.
fuente
Math::GMP
de una manera que no es tan derrochadora con la creación / destrucción de referencias mpz.$x = new Math::GMP(0); $x += 3 for 1..1000000
. Publicaré en cpan cuando termine; serás uno de los primeros en saber;)