Exponentiation rapide
Lorsque l'on souhaite calculer $a^n$, on peut naïvement effectuer $n-1$ multiplications en effectuant le produit :
Cependant, l'exemple suivant montre que l'on peut calculer $a^{2048}$ en effectuant simplement 11 multiplications (chaque fois que l'on élève au carré) :
L'algorithme d'exponentiation rapide est la transposition au cas général de l'exemple précédent. Une version récursive est donnée par :
- si $n=0$, alors $a^n=1$.
- si $n=2p$ est pair, alors $a^n=(a^p)^2$.
- si $n=2p+1$ est impair, alors $a^n=(a^p)^2\times a$.
Alors que l'algorithme naïf demande de l'ordre de $n$ multiplications pour calculer $a^n$, l'algorithme d'exponentiation rapide se contente de l'ordre de $\ln(n)$ multiplications. En outre, tester si un entier est pair est très rapide sur un ordinateur.
Consulter aussi...