Cuando se computa con exponentes muy grandes (> 150) con un número entero pequeño, ¿es mejor utilizar la aritmética de precisión arbitraria o la exponenciación modular?

Answer 1

Si solo está interesado en x ^ n mod p, donde x y p son relativamente pequeños (digamos, encajan en el registro de 32 bits), entonces usaría un algoritmo con complejidad O (lg n), como este:

function pow(x,n,p){

if (n==0) {

return 1

}

half = pow(x,floor(n/2),p)

full = half * half mod p

if (n is even) {

return full

} else {

return full * x mod p

}

}

Hay muchas formas diferentes en que este algoritmo puede reformularse (por ejemplo, puede pasar x * x a la llamada recursiva, o reemplazar la recursión con iteración y escaneo de bits, etc.) y aún mantener el tiempo de ejecución O (lg n).

En mi experiencia, la operación más costosa es la operación de módulo (ya que la división solía ser 30 veces más lenta que la multiplicación), pero en algunos idiomas la operación más costosa podría ser la llamada a función, por lo que es posible que desee reescribirla usando un bucle.

Answer 2

Debería explicar mejor el contexto de su cálculo. ¿Qué necesitas para calcular exactamente? x ^ n, con x pequeño yn grande? Entonces, por supuesto, necesita aritmética de precisión arbitraria. La exponenciación modular es lo que necesita, si solo está interesado en el módulo restante, algunos enteros más pequeños. Intenta enfocar tu interés, si quieres una respuesta más significativa. Y piénselo: las matemáticas son algo que es mejor escribir matemáticamente, con una fórmula: escribir letras sobre matemáticas es como describir Linux en un poema. Puede disfrutarlo, pero nunca podrá usarlo correctamente …