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.

Power

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

Références