L'exponentiation rapide, prouvée et comptée

/* Renvoie x elevee a la puissance n.
   Precondition  : n >= 0.
   Postcondition : le resultat vaut x^n, au debordement des long pres. */
long puissance(long x, int n) {
    assert(n >= 0);
    long r = 1, b = x;
    int e = n;
    /* INVARIANT : r * b^e == x^n, et e >= 0.     VARIANT : e. */
    while (e > 0) {
        if (e % 2 == 1) { r = r * b; }
        b = b * b;
        e = e / 2;
    }
    return r;
}

Terminaison. Variant $V=e$ : entier, positif tant que la condition tient, et divisé par deux à chaque tour, donc strictement décroissant dès que $e\ge 1$. La boucle fait exactement $\lfloor {\log }_{2}n\rfloor +1$ tours pour $n\ge 1$.

Correction. Initialisation : $r=1$, $b=x$, $e=n$, donc $r{b}^e=x^n$. Conservation : soit $r{b}^e=x^n$ en début de tour.

• Si $e$ est pair, $e=2q$ : le tour pose $b^{\prime }=b^2$ et $e^{\prime }=q$, d'où $r^{\prime }{b}^{\prime e^{\prime }}=r(b^2{)}^q=r{b}^{2q}=r{b}^e=x^n$.
• Si $e$ est impair, $e=2q+1$ : le tour pose $r^{\prime }=rb$, $b^{\prime }=b^2$, $e^{\prime }=q$, d'où $r^{\prime }{b}^{\prime e^{\prime }}=rb(b^2{)}^q=r{b}^{2q+1}=x^n$.

Utilisation : à la sortie, $e=0$, donc $b^e=1$ et l'invariant devient $r=x^n$. C'est la postcondition.

Complexité, exactement. Le tour d'indice $k$ fait une élévation au carré, plus une multiplication si le bit $k$ de $n$ vaut $1$. Le nombre total de multiplications est donc

$$\underset{\text{les carreˊs}}{\underbrace{\lfloor {\log }_{2}n\rfloor +1}}+\underset{\text{les bits aˋ }1}{\underbrace{s_2(n)}},$$

où $s_2(n)$ est le nombre de $1$ dans l'écriture binaire de $n$. La mesure confirme la formule à l'unité près :

       n | binaire        | rapide | naive
       1 | 1              |      2 |       1
       7 | 111            |      6 |       7
       8 | 1000           |      5 |       8
      15 | 1111           |      8 |      15
      16 | 10000          |      6 |      16
     100 | 1100100        |     10 |     100
    1000 | 1111101000     |     16 |    1000
 1000000 | (20 bits, 7 a 1)|    27 | 1000000

Pour $n=10^6$ : 27 multiplications au lieu d'un million.