L' exponentiation rapide calcule en lisant l'écriture binaire de

L'idée. $x^n={\prod }_{i:a_i=1}{x}^{2^i}$, où les $a_i$ sont les bits de $n$. On maintient un facteur qui vaut successivement $x$, $x^2$, $x^4$, $x^8$… et on ne le multiplie au résultat que lorsque le bit courant vaut $1$.

def puissance_rapide(x, n):
    """x**n par l'écriture binaire de n. Précondition : n >= 0."""
    assert n >= 0
    resultat = 1
    facteur = x
    while n > 0:
        if n % 2 == 1:
            resultat = resultat * facteur
        facteur = facteur * facteur
        n = n // 2
    return resultat

for x in range(-4, 5):
    for n in range(0, 20):
        assert puissance_rapide(x, n) == x**n

$180$ cas passent.

L'invariant. À chaque tour, $\text{resultat}\times {\text{facteur}}^n=x^{n_0}$ où $n_0$ est l'exposant initial. Au dernier tour $n=0$, donc $\text{resultat}=x^{n_0}$ : c'est ce qui prouve la fonction.

Le coût. La boucle fait $\lfloor {\log }_{2}n\rfloor +1$ tours — soit nb_bits(n), la fonction du cours. Pour $n=13$ : $4$ tours. Pour $n=1000$ : $10$ tours, là où la méthode naïve en ferait $999$.

Contrôle : puissance_rapide(3, 13) rend $1594323$, et $3^{13}=1594323$.

Prolongement : ce passage de $n$ à ${\log }_{2}n$ est le gain de la dichotomie, que le chapitre 8 retrouvera sur la recherche dans un tableau trié.