Si tengo un número entero N del que conozco la factorización, ¿cuál es la forma más rápida (más eficiente) de calcular 1/N como un número de coma flotante? Para eso, se debe usar la aritmética flotante grande (o de enteros).
Quiero hacer esto en C++ (o hacer ejecuciones experimentales en Python).
Mi N es muy grande, Giga/Tera-bits de tamaño. El punto flotante N resultante también debe tener una gran precisión, aproximadamente del mismo tamaño de bits que el N inicial.
Se necesita un valor flotante preciso, lo que significa que si solicito bits Log2(N) de precisión flotante, al menos el 95% de los bits principales del resultado deben ser precisos (todos los mismos bits que en el valor ideal).
Por supuesto, en lugar del cálculo de coma flotante, se puede calcular 4^Ceil(Log2(N)) / N como división entera, si ayuda y/o simplifica la tarea. Para mí, estas dos tareas (entero y flotante) son esencialmente las mismas, porque la representación de enteros se puede convertir en flotante y viceversa.
Una nota importante es que la factorización de N solo tiene factores primos pequeños, todos ellos tienen un tamaño de 32 bits (tal vez 64 bits como máximo, seguro).
Me pregunto si tener factorización de N y también el hecho de que los factores son pequeños, ¿puede ayudar de alguna manera a resolver la tarea?
Por supuesto, en lugar de implementar mi propia división primero, traté de usar una biblioteca GMP altamente optimizada para esta tarea, pero (que yo sepa) no usa el hecho de que N ya está factorizado.
¿Alguien puede sugerir si estoy a punto de implementar mi propia función para esto, solo para descubrir experimentalmente si será más rápido que GMP, entonces qué tipo de algoritmo debo usar?
Descubrí que hay 3 algoritmos que se pueden usar aquí 1) División larga , que es un algoritmo de grado escolar. 2) Reducción de Barrett . 3) Reducción de Montgomery .
En realidad no conozco ningún otro algoritmo. ¿Puedes sugerir otro? Tanto las reducciones de Barrett como las de Montgomery pueden ayudar solo si el mismo factor primo se repite muchas veces; de lo contrario, la división de tiempo único no vale el cálculo previo que se necesita para Barrett y Montgomery.
Además, las reducciones de Barrett/Montgomery aún necesitan computación única 4^Ceil(Log2(N)) / PrimeDivisor . Entonces no te salvan de hacer el algoritmo de división larga.
Definitivamente, para el algoritmo de división larga, usaré 2^64 como base en lugar de la base 10 (como en la escuela).
Ya implementé mi propia biblioteca experimental con división larga y todos los demás algoritmos de aritmética de enteros, además de aritmética de curva elíptica. En este momento es genérico y, por lo tanto, no es más rápido que GMP. Ahora necesito un algoritmo de división especial que pueda ser al menos varias veces más rápido que GMP.
Seguro que en Long Division puedo usar Montgomery y Barrett, porque en cada paso necesita una división corta (entero de 128 bits dividido por un entero de 64 bits) si da algún impulso.
También en cada paso de la división larga puedo usar la transformada rápida de Fourier o la transformada teórica de números para hacer la multiplicación.
Arriba están las únicas optimizaciones que conozco. ¿Existen otras optimizaciones posibles? ¿Quizás FFT se puede usar para hacer divisiones directamente (no solo para multiplicar)?