Por que pow (a, d, n) é tão mais rápido que a ** d% n?

Eu estava tentando implementar um teste de primalidade Miller-Rabin e fiquei intrigado por que estava demorando tanto (> 20 segundos) para números de tamanho médio (~ 7 dígitos). Acabei descobrindo que a seguinte linha de código é a origem do problema:

x = a**d % n

(onde a,, de nsão todos semelhantes, mas desiguais, números de tamanho médio, **é o operador de exponenciação e %é o operador de módulo)

Em seguida, tentei substituí-lo pelo seguinte:

x = pow(a, d, n)

e, em comparação, é quase instantâneo.

Para contexto, aqui está a função 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))

Um exemplo 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)})

Resultado (executado com PyPy 1.9.0):

2642565
time: 23.785543s
2642565
time: 0.000030s

Saída (executado com Python 3.3.0, 2.7.2 retorna tempos muito semelhantes):

2642565
time: 14.426975s
2642565
time: 0.000021s

E uma questão relacionada, por que esse cálculo é quase duas vezes mais rápido quando executado com Python 2 ou 3 do que com PyPy, quando geralmente PyPy é muito mais rápido ?

Veja o artigo da Wikipedia sobre exponenciação modular . Basicamente, quando você faz isso a**d % n, você realmente tem que calcular a**d, o que pode ser muito grande. Mas existem maneiras de computar a**d % nsem precisar computar a a**dsi mesmo, e é isso que powacontece. O **operador não pode fazer isso porque ele não pode "ver o futuro" para saber que você vai tomar o módulo imediatamente.

BrenBarn respondeu à sua pergunta principal. Para sua parte:

por que é quase duas vezes mais rápido quando executado com Python 2 ou 3 do que PyPy, quando geralmente PyPy é muito mais rápido?

Se você ler a página de desempenho do PyPy , esse é exatamente o tipo de coisa em que o PyPy não é bom - na verdade, o primeiro exemplo que eles dão:

Exemplos ruins incluem fazer cálculos com longos longos - que é executado por código de suporte não otimizado.

Teoricamente, transformar uma exponenciação enorme seguida por um mod em uma exponenciação modular (pelo menos após a primeira passagem) é uma transformação que um JIT pode ser capaz de fazer ... mas não o JIT de PyPy.

Como uma observação lateral, se você precisa fazer cálculos com números inteiros enormes, você pode querer olhar para módulos de terceiros como gmpy, que às vezes pode ser muito mais rápido do que a implementação nativa do CPython em alguns casos fora dos usos principais, e também tem muito de funcionalidade adicional que você mesmo teria que escrever, ao custo de ser menos conveniente.

Existem atalhos para fazer a exponenciação modular: por exemplo, você pode encontrar a**(2i) mod npara cada ide 1a log(d)e multiplicar (mod n) os resultados intermediários de que precisa. Uma função de exponenciação modular dedicada como 3 argumentos pow()pode alavancar tais truques porque sabe que você está fazendo aritmética modular. O analisador Python não pode reconhecer isso dada a expressão nua a**d % n, então ele executará o cálculo completo (o que levará muito mais tempo).

O modo como x = a**d % nse calcula é elevar aà dpotência, então módulo isso com n. Em primeiro lugar, se afor grande, isso cria um grande número que é truncado. No entanto, x = pow(a, d, n)é mais provável que seja otimizado para que apenas os últimos ndígitos sejam rastreados, que são tudo o que é necessário para calcular o módulo de multiplicação de um número.