Pourquoi est-pow (a, d, n) beaucoup plus rapide qu’un ** d % n ?

Question

J'ai essayé de mettre en œuvre un Miller-Rabin test de primalité, et a demandé pourquoi c'était si long (> 20 secondes) pour les moyennes des nombres (~7 chiffres). J'ai fini par trouver la ligne de code suivante à la source du problème:

x = a**d % n

(où a, d, et n sont tous semblables, mais inégale, de taille moyenne nombre, ** est l'opérateur exponentiel, et % est l'opérateur modulo)

J'ai ensuite j'ai essayé de le remplacer par le suivant:

x = pow(a, d, n)

et par comparaison, il est presque instantanée.

Pour le contexte, ici, c'est la fonction d'origine:

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 exemple de calcul cadencées:

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

De sortie (courir avec PyPy 1.9.0):

2642565
time: 23.785543s
2642565
time: 0.000030s

De sortie (courir avec Python 3.3.0, 2.7.2 retourne très semblable fois):

2642565
time: 14.426975s
2642565
time: 0.000021s

Et une question, pourquoi est ce calcul presque deux fois plus rapide lors de l'exécution avec Python 2 ou 3 que avec PyPy, quand habituellement PyPy est beaucoup plus rapide?

Answer 1

Voir l'article Wikipedia sur l'exponentiation modulaire. Fondamentalement, lorsque vous n' a**d % n, vous devez calculer a**d, qui pourrait être assez important. Mais il existe des moyens de calcul a**d % n sans avoir à calculer a**d lui-même, et c'est ce qu' pow . L' ** opérateur ne peut pas le faire, car il ne peut pas "voir l'avenir" de savoir que vous allez prendre immédiatement le module.

Answer 2

BrenBarn répondu à votre question principale. Pour votre part:

pourquoi est-il presque deux fois plus rapide lors de l'exécution avec Python 2 ou 3 que PyPy, quand habituellement PyPy est beaucoup plus rapide?

Si vous lisez PyPy est la page des performances, c'est exactement le genre de chose que PyPy est pas bon en fait, le tout premier exemple qu'ils donnent:

Mauvais exemples incluent faisant les calculs avec les grands longs – qui est effectuée par l'unoptimizable code de support.

Théoriquement, transformer une grande exponentiation suivie par un mod dans une exponentiation modulaire (au moins après la première passe) est une transformation d'une équipe commune d'enquête peut être en mesure de faire... mais pas PyPy JIT.

Comme une note de côté, si vous avez besoin de faire des calculs avec d'énormes entiers, vous pouvez regarder des modules tiers, comme gmpy, ce qui peut parfois être beaucoup plus rapide Disponible natif de mise en œuvre, dans certains cas, en dehors du courant dominant utilise, et a également un grand nombre de fonctionnalités supplémentaires que vous auriez autrement à écrire vous-même, au prix d'être moins pratique.

Answer 3

Il y a des raccourcis pour faire de l'exponentiation modulaire: par exemple, vous pouvez trouver a**(2i) mod n pour chaque i de 1 de log(d) et multiplier (mod n), les résultats intermédiaires dont vous avez besoin. Un dédié modulaire-exponentiation fonction 3-argument pow() peuvent tirer parti de ces tours-là parce qu'il sait que vous êtes en train de faire l'arithmétique modulaire. Le Python analyseur ne peut pas reconnaître cela, étant donné la nue expression a**d % n, alors il va effectuer le calcul complet (ce qui prendra beaucoup plus de temps).

Answer 4

La façon dont est calculée est de recueillir des à la puissance, puis modulo qu’avec . Tout d’abord, si est grande, cela crée un grand nombre qui est ensuite tronqué. Cependant, est très probablement optimisé de sorte que seuls les derniers `` chiffres sont suivis, qui sont tous ceux qui sont requis pour le calcul de la multiplication modulo un nombre.