Pourquoi pow (a, d, n) est-il tellement plus rapide que a ** d% n?

110

J'essayais de mettre en œuvre un test de primalité de Miller-Rabin et j'étais perplexe sur la raison pour laquelle cela prenait si longtemps (> 20 secondes) pour les nombres de taille moyenne (~ 7 chiffres). J'ai finalement trouvé que la ligne de code suivante était la source du problème:

x = a**d % n

(où a, det nsont tous similaires, mais inégaux, des nombres de taille moyenne, **est l'opérateur d'exponentiation et %est l'opérateur modulo)

J'ai ensuite essayé de le remplacer par ce qui suit:

x = pow(a, d, n)

et c'est par comparaison presque instantané.

Pour le contexte, voici 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 chronométré:

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

Sortie (exécutée avec PyPy 1.9.0):

2642565
time: 23.785543s
2642565
time: 0.000030s

Sortie (exécutée avec Python 3.3.0, 2.7.2 renvoie des temps très similaires):

2642565
time: 14.426975s
2642565
time: 0.000021s

Et une question connexe, pourquoi ce calcul est-il presque deux fois plus rapide lorsqu'il est exécuté avec Python 2 ou 3 qu'avec PyPy, alors que PyPy est généralement beaucoup plus rapide ?

lyallcooper
la source

Réponses:

164

Voir l'article de Wikipedia sur l'exponentiation modulaire . Fondamentalement, lorsque vous le faites a**d % n, vous devez en fait calculer a**d, ce qui peut être assez important. Mais il existe des moyens de calculer a**d % nsans avoir à se calculer a**dlui-même, et c'est ce qui powfait. L' **opérateur ne peut pas faire cela car il ne peut pas "voir dans le futur" pour savoir que vous allez immédiatement prendre le module.

BrenBarn
la source
14
+1 c'est en fait ce que la docstring implique>>> print pow.__doc__ pow(x, y[, z]) -> number With two arguments, equivalent to x**y. With three arguments, equivalent to (x**y) % z, but may be more efficient (e.g. for longs).
Hedde van der Heide
6
Selon votre version de Python, cela ne peut être vrai que dans certaines conditions. IIRC, dans 3.x et 2.7, vous ne pouvez utiliser que la forme à trois arguments avec des types intégraux (et une puissance non négative), et vous obtiendrez toujours une exponentiation modulaire avec le inttype natif , mais pas nécessairement avec d'autres types intégraux. Mais dans les anciennes versions, il y avait des règles sur l'ajustement dans un C long, la forme à trois arguments était autorisée float, etc. (J'espère que vous n'utilisez pas la version 2.1 ou antérieure, et que vous n'utilisez pas de types intégraux personnalisés des modules C, donc aucun de cela compte pour vous.)
abarnert
13
D'après votre réponse, il semble qu'il soit impossible pour un compilateur de voir l'expression et de l'optimiser, ce qui n'est pas vrai. Il arrive juste qu'aucun compilateur Python actuel ne le fasse.
danielkza
5
@danielkza: C'est vrai, je ne voulais pas dire que c'est théoriquement impossible. Peut-être que «ne regarde pas dans le futur» serait plus précis que «ne peut pas voir dans le futur». Notez cependant que l'optimisation peut être extrêmement difficile voire impossible en général. Pour les opérandes constants, il pourrait être optimisé, mais dans x ** y % n, xpourrait être un objet qui implémente __pow__et, basé sur un nombre aléatoire, renvoie l'un des différents objets implémentés __mod__d'une manière qui dépend également de nombres aléatoires, etc.
BrenBarn
2
@danielkza: De plus, les fonctions n'ont pas le même domaine: .3 ** .4 % .5c'est parfaitement légal, mais si le compilateur le transformait, cela lèverait pow(.3, .4, .5)un TypeError. Le compilateur devrait être en mesure de savoir que a, det nsont garantis être les valeurs d'un type intégral (ou peut - être juste en particulier de type int, parce que la transformation ne permet pas autrement), et dest garanti à être négatif. C'est quelque chose qu'un JIT pourrait faire, mais un compilateur statique pour un langage avec des types dynamiques et aucune inférence ne peut tout simplement pas.
abarnert le
37

BrenBarn a répondu à votre question principale. Pour votre côté:

pourquoi est-il presque deux fois plus rapide lorsqu'il est exécuté avec Python 2 ou 3 que PyPy, alors que PyPy est généralement beaucoup plus rapide?

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

Les mauvais exemples incluent les calculs avec des longs longs - qui sont effectués par un code de support non optimisable.

Théoriquement, transformer une énorme exponentiation suivie d'un mod en une exponentiation modulaire (au moins après la première passe) est une transformation qu'un JIT pourrait être capable de faire… mais pas le JIT de PyPy.

En remarque, si vous avez besoin de faire des calculs avec d'énormes entiers, vous voudrez peut-être regarder des modules tiers comme gmpy, qui peuvent parfois être beaucoup plus rapides que l'implémentation native de CPython dans certains cas en dehors des utilisations traditionnelles, et qui en ont également beaucoup de fonctionnalités supplémentaires que vous auriez autrement à écrire vous-même, au prix d'être moins pratique.

Abarnert
la source
2
les longs ont été fixés. essayez pypy 2.0 beta 1 (ce ne sera pas plus rapide que CPython, mais ne devrait pas non plus être plus lent). gmpy n'a pas de moyen de gérer MemoryError :(
fijal
@fijal: Oui, et gmpyest également plus lent au lieu de plus rapide dans quelques cas, et rend beaucoup de choses simples moins pratiques. Ce n'est pas toujours la réponse - mais c'est parfois le cas. Cela vaut donc la peine de regarder si vous avez affaire à d'énormes entiers et que le type natif de Python ne semble pas assez rapide.
abarnert le
1
et si vous ne vous souciez pas de savoir si vos chiffres sont élevés, votre programme est en
panne
1
C'est le facteur qui a empêché PyPy d'utiliser la bibliothèque GMP pendant longtemps. Cela peut vous convenir, cela ne convient pas aux développeurs de machines virtuelles Python. Le malloc peut échouer sans utiliser beaucoup de RAM, il suffit d'en mettre un très grand nombre. Le comportement de GMP à partir de ce moment est indéfini et Python ne peut pas le permettre.
fijal
1
@fijal: Je suis tout à fait d'accord qu'il ne devrait pas être utilisé pour implémenter le type intégré de Python. Cela ne veut pas dire qu'il ne devrait jamais être utilisé pour quoi que ce soit.
abarnert le
11

Il existe des raccourcis pour faire l'exponentiation modulaire: par exemple, vous pouvez trouver a**(2i) mod npour chaque ide 1à log(d)et multiplier ensemble (mod n) les résultats intermédiaires dont vous avez besoin. Une fonction d'exponentiation modulaire dédiée telle que 3 arguments pow()peut tirer parti de ces astuces car elle sait que vous faites de l'arithmétique modulaire. L'analyseur Python ne peut pas reconnaître cela étant donné l'expression nue a**d % n, il effectuera donc le calcul complet (ce qui prendra beaucoup plus de temps).

atomicinf
la source
3

Le moyen de x = a**d % ncalculer est de monter aà la dpuissance, puis modulo cela avec n. Premièrement, si aest grand, cela crée un nombre énorme qui est ensuite tronqué. Cependant, x = pow(a, d, n)est très probablement optimisé pour que seuls les derniers nchiffres soient suivis, qui sont tout ce qui est nécessaire pour calculer la multiplication modulo un nombre.

Yuushi
la source
6
"il faut d multiplications pour calculer x ** d" - incorrect. Vous pouvez le faire en multiplications O (log d) (très larges). L'exponentiation par quadrillage peut être utilisée sans module. La taille même des multiplicandes est ce qui prend la tête ici.
John Dvorak
@JanDvorak Vrai, je ne sais pas pourquoi je pensais que python n'utiliserait pas le même algorithme d'exponentiation pour **et pour pow.
Yuushi
5
Pas les derniers chiffres "n" .. il garde juste les calculs en Z / nZ.
Thomas le