Escriba un programa de ensamblaje GOLF que lea un número entero de stdin (seguido de una nueva línea final) y genere sus factores primos separados por nuevas líneas, seguidas de una nueva línea final en stdout.
Los factores primos no necesitan estar en un orden particular. 1
No es un factor primo.
Su binario GOLF (después del ensamblaje) debe caber en 8192 bytes.
Su programa se puntuará ejecutándolo 10 veces, cada uno con una de las siguientes entradas:
8831269065180497
2843901546547359024
6111061272747645669
11554045868611683619
6764921230558061729
16870180535862877896
3778974635503891117
204667546124958269
16927447722109721827
9929766466606501253
Estos números están ordenados en términos de dificultad. El primero debería resolverse fácilmente por división de prueba.
La optimización hacia este conjunto de números va en contra del espíritu de la pregunta, puedo cambiar el conjunto de números en cualquier momento. Su programa debe funcionar para cualquier número de entrada positivo de 64 bits, no solo estos.
Su puntaje es la suma de los ciclos de CPU utilizados para factorizar los números anteriores.
Como GOLF es muy nuevo, incluiré algunos consejos aquí. Debe leer la especificación GOLF con todas las instrucciones y los costos del ciclo . En el repositorio de Github se pueden encontrar programas de ejemplo. En particular, mire el programa de ejemplo factorial , que demuestra entrada / salida.
Compile su programa en un binario ejecutando python3 assemble.py your_source.golf
. Luego ejecute su programa usando python3 golf.py your_source.bin
, esto también debería imprimir el conteo del ciclo. Vea los valores del contenido del registro a la salida del programa con la -d
bandera - use --help
para ver todas las banderas.
1
no es un factor primo, ¿debería imprimir solo el entero de entrada?Respuestas:
2,279,635 ciclos — 7373 bytes (determinista)
Uno a uno:
Resumen:
Utilizo una combinación de la división de prueba y el algoritmo rho de Brent-Pollard para la factorización, y la búsqueda de tablas más Miller-Rabin para las pruebas de primalidad. Agregaré más explicaciones mañana.
Tenga en cuenta que debido al límite de caracteres en la longitud de la publicación, la segunda tabla de datos se trunca. Esta esencia incluye la tabla completa.
fuente
mov o, 42
Es un regalo muerto.Total 36,757,269,913 ciclos
830B ensamblado
Factorización por división de prueba, con algunas optimizaciones. Probablemente no sea el más rápido, pero como nadie más ha publicado aún, lo comenzaré.
Salida completa de mi ciclo de tiempo, en caso de que alguien quiera verificar los resultados y / o copiar y pegar y matemáticas
fuente
divu
: stackoverflow.com/questions/5558492/… . En cuanto a su respuesta, esta pregunta no fue resuelta mediante la división de prueba: Pfactor * factor < number
: ningún número puede tener factores mayores que la raíz cuadrada.puntaje = 378,867,816 ciclos
[aleatorizado - sus resultados pueden variar]
Utiliza la prueba de primalidad de Miller-Rabin (una versión determinista que puede manejar hasta 2 ^ 64), un poco de factoring de prueba y factoring ECM . Todas las operaciones algebraicas están allí, incluidas la suma modular, la resta, la multiplicación, la exponenciación y la inversión (mod n <2 ^ 64).
La multiplicación modular es subóptima: realiza una búsqueda binaria del cociente. Calcular el resto de una división de 128 por 64 es difícil sin una instrucción integrada correspondiente. Acelera eso y todo irá más rápido.
2290 bytes compilados
Salida:
fuente