javascript-algorithms
Algorithme d’exponentiation rapide
Read this in other languages: english.
En algèbre, une puissance d’un nombre est le résultat de la multiplication répétée de ce nombre avec lui-même.
Elle est souvent notée en assortissant le nombre d’un entier, typographié en exposant, qui indique le nombre de fois qu’apparaît le nombre comme facteur dans cette multiplication.
Implémentation « naïve »
Comment trouver a élevé à la puissance b ?
On multiplie a avec lui-même, b nombre de fois.
Ainsi, a^b = a * a * a * ... * a (b occurrences de a).
Cette opération aura un complexité linéaire, notée O(n),
car la multiplication aura lieu exactement n fois.
Algorithme d’exponentiation rapide
Peut-on faire mieux que cette implémentation naïve?
Oui, on peut réduire le nombre de puissance à un complexité de O(log(n)).
Cet algorithme utilise l’approche « diviser pour mieux régner »
pour calculer cette puissance.
En l’état, cet algorithme fonctionne pour deux entiers positifs X et Y.
L’idée derrière cet algorithme est basée sur l’observation suivante.
Lorsque Y est pair:
X^Y = X^(Y/2) * X^(Y/2)
Lorsque Y est impair:
X^Y = X^(Y//2) * X^(Y//2) * X
où Y//2 est le résultat de la division entière de Y par 2.
Par exemple
2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2)
2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2)
Ainsi, puisqu’à chaque étape on doits calculer
deux fois la même puissance X ^ (Y / 2),
on peut optimiser en l’enregistrant dans une variable intermédiaire
pour éviter son calcul en double.
Complexité en temps
Comme à chaque itération nous réduisons la puissance de moitié,
nous appelons récursivement la fonction log(n) fois. Le complexité de temps de cet algorithme est donc réduite à:
O(log(n))