Estoy tratando de encontrar una manera de calcular $a! \bmod b$ donde $0<a<b$ para un tamaño arbitrario de $a$ . ¿Existe una manera eficiente de hacer esto sin calcular $a!$ ¿Explícitamente?
Respuestas
¿Demasiados anuncios?
mathreadler
Puntos
3517
N! se hace grande ya para valores pequeños de n por lo que el almacenamiento se convierte rápidamente en un problema si tuviéramos que calcular y almacenar el número entero antes de hacer el módulo. La idea de Mose Wintner en los comentarios evita tener que almacenar el número entero, lo que está muy bien, aunque también podemos hacerlo por pares y en cualquier orden, por ejemplo $$(1 \cdot 2) (3 \cdot 4) (5 \cdot 6) (7 \cdot 8) (\text{mod 11})$$ Que es igual a $$(1 \cdot 2 (\text{mod 11})) (3 \cdot 4 (\text{mod 11})) (5 \cdot 6 (\text{mod 11})) (7 \cdot 8 (\text{mod 11}))$$
De este modo, si $n$ es grande y tenemos un ordenador de muchos núcleos podemos hacer cada multiplicación-módulo de forma independiente y luego recurrir a los productos anteriores, reduciendo a la mitad el número de factores en cada paso.
Implementar la idea de Mose Wintner en el lenguaje C con 4 pthreads en mi ordenador de 2 núcleos para $$100000001 ! = 68124726 (\text{mod } 179425133)$$ tarda unos 2 segundos, pero eso es mientras estoy haciendo un montón de otros trabajos por lotes al mismo tiempo. No tengo ningún software de precisión simbólica o de int grande para comparar, pero debería estar dentro del margen "largo" de 64 bits ( creo ). Lo he comprobado para algunos números más pequeños y me ha dado los mismos resultados que octave, pero he tenido que aumentar el tamaño para poder medir la velocidad, ya que era demasiado rápido para medir la velocidad de forma fiable para los números más pequeños.
gnasher729
Puntos
3414
Con "arbitrariamente grande" asumo un >> $10^{12}$ ¿o algo así? ¿Lo que significa que b también es grande?
Yo empezaría por factorizar b; si b tiene un factor $p^k$ con p ≤ a entonces podremos demostrar que a! = 0 (modulo $p^k$ ). Incluso si no es el caso, calcular un módulo x en un ordenador actual será mucho más rápido si x < $2^{64}$ . A continuación, se pueden combinar varios resultados.
¡Ahora suponemos que queremos un! (módulo b) donde a < b y b no puede ser razonablemente factorizado. Obviamente, podemos calcular un producto de un gran número de enteros (módulo b) realizando cada una de las multiplicaciones módulo b. Si $a^2$ < b entonces podemos multiplicar números por pares.
Cuando a es grande, intentaríamos distribuir el cálculo entre varios procesadores, lo que es bastante trivial. También realizaríamos múltiples multiplicaciones (módulo b) en paralelo para utilizar la capacidad de cada procesador de realizar múltiples operaciones en paralelo.
Para calcular (ax) módulo b, tendríamos que calcular ax, dividir por b, redondear a un número entero y restar ese número entero por b del producto. Será más rápido calcular 1/b una vez y puede ser más rápido no redondear (ax / b) hacia abajo, sino redondear (ax * (1/b)) a un entero cercano. En realidad no Necesito (ax) módulo b, es suficiente si tenemos un número pequeño z con z módulo b = (ax) módulo b.
Ian Miller
Puntos
3708
Hay ciertos casos que se pueden evaluar fácilmente, sin embargo, para la mayoría de los casos habría que evaluarlos recursivamente. Aplicar el mod después de cada paso recursivo ayudará con el almacenamiento del valor.
Casos especiales:
La respuesta será cero si hay suficientes términos para cubrir la factorización prima de $b$ . Por ejemplo, si $b=72$ necesitas tres factores de 2 y dos factores de 3.
Si $b$ es primo y $a=b-1$ entonces la respuesta es $a-1$ .
Si $b$ es primo y $a=b-2$ entonces la respuesta es 1.
