python - pypy tutorial

¿Por qué es pow(a, d, n) mucho más rápido que a** d% n?

Question

Estaba tratando de implementar una prueba de primalidad Miller-Rabin , y me sorprendió por qué tardaba tanto (> 20 segundos) en números medianos (~ 7 dígitos). Eventualmente encontré la siguiente línea de código para ser la fuente del problema:

x = a**d % n

(donde a , d n son todos similares, pero desiguales, números medianos, ** es el operador de exponenciación, y % es el operador de módulo)

Luego intenté reemplazarlo con lo siguiente:

x = pow(a, d, n)

y en comparación es casi instantáneo.

Para el contexto, aquí está la función original:

from random import randint

def primalityTest(n, k):
    if n < 2:
        return False
    if n % 2 == 0:
        return False
    s = 0
    d = n - 1
    while d % 2 == 0:
        s += 1
        d >>= 1
    for i in range(k):
        rand = randint(2, n - 2)
        x = rand**d % n         # offending line
        if x == 1 or x == n - 1:
            continue
        for r in range(s):
            toReturn = True
            x = pow(x, 2, n)
            if x == 1:
                return False
            if x == n - 1:
                toReturn = False
                break
        if toReturn:
            return False
    return True

print(primalityTest(2700643,1))

Un ejemplo de cálculo cronometrado:

from timeit import timeit

a = 2505626
d = 1520321
n = 2700643

def testA():
    print(a**d % n)

def testB():
    print(pow(a, d, n))

print("time: %(time)fs" % {"time":timeit("testA()", setup="from __main__ import testA", number=1)})
print("time: %(time)fs" % {"time":timeit("testB()", setup="from __main__ import testB", number=1)})

Salida (ejecutada con PyPy 1.9.0):

2642565
time: 23.785543s
2642565
time: 0.000030s

Salida (ejecutar con Python 3.3.0, 2.7.2 devuelve tiempos muy similares):

2642565
time: 14.426975s
2642565
time: 0.000021s

Y una pregunta relacionada, ¿por qué este cálculo es casi el doble de rápido cuando se ejecuta con Python 2 o 3 que con PyPy, cuando por lo general PyPy es mucho más rápido ?

Answer 1

BrenBarn respondió tu pregunta principal. Para tu lado:

¿Por qué es casi el doble de rápido cuando se ejecuta con Python 2 o 3 que con PyPy, cuando por lo general PyPy es mucho más rápido?

Si lees la página de rendimiento de PyPy, este es exactamente el tipo de cosas en las que PyPy no es bueno, de hecho, el primer ejemplo que dan:

Los malos ejemplos incluyen realizar cálculos con largos largos, que se realiza mediante un código de soporte no optimizable.

Teóricamente, convertir una gran exponenciación seguida de un mod en una exponenciación modular (al menos después del primer pase) es una transformación que un JIT podría hacer ... pero no el JIT de PyPy.

Como nota al margen, si necesita hacer cálculos con enteros enormes, es posible que desee ver módulos de terceros como gmpy , que a veces puede ser mucho más rápido que la implementación nativa de CPython en algunos casos fuera de los usos principales, y también tiene un mucha funcionalidad adicional que de otra manera tendrías que escribir tú mismo, a costa de ser menos conveniente.

Answer 2

Hay métodos abreviados para hacer una exponenciación modular: por ejemplo, puede encontrar a**(2i) mod n para cada i de 1 a log(d) y multiplicar juntos (mod n ) los resultados intermedios que necesita. Una función de exponenciación modular dedicada como 3 argumentos pow() puede aprovechar estos trucos porque sabe que está haciendo aritmética modular. El analizador de Python no puede reconocer esto dada la expresión desnuda a**d % n , por lo que realizará el cálculo completo (que llevará mucho más tiempo).

Answer 3

La forma en que x = a**d % n se calcula es elevar a la potencia d , luego modulo que con n . En primer lugar, si a es grande, esto crea un gran número que luego se trunca. Sin embargo, es muy probable que x = pow(a, d, n) se optimice de manera que solo se rastreen los últimos n dígitos, que son todo lo que se requiere para calcular el número de multiplicación de un número.

Answer 4

Vea el artículo de Wikipedia sobre exponenciación modular . Básicamente, cuando haces a**d % n , en realidad tienes que calcular a**d , que podría ser bastante grande. Pero hay formas de calcular a**d % n sin tener que calcular a**d sí mismo, y eso es lo que hace pow . El operador ** no puede hacer esto porque no puede "ver hacia el futuro" para saber que va a tomar el módulo inmediatamente.