Étude : exponentiation

On va étudier deux algorithmes permettant de calculer $a^b$ à partir de deux entiers $a$ et $b$. Pour chaque algorithme on étudiera son fonctionnement selon 3 axes :

• fonctionnement
• preuve
• complexité

Algorithme naïf

Le calcul naïf de l'exponentielle est basé sur sa définition mathématique, qui peut être décrite, pour deux entiers strictement positifs $x$ et $n$, par l'équation suivante :

Bien que non nécessaire, la contrainte de positivité stricte pour $x$ et $n$ nous permet d'éviter tout cas particulier qui pourrait (tôt ou tard) advenir dans les preuves lorsque $x$ ou $n$ vaut 0.

algorithme puissance(nombre: entier, exposant: entier) → entier:
    si exposant == 1:
        rendre nombre
    rendre nombre * puissance(nombre, exposant - 1)

Pour cette étude, nous allons uniquement utiliser des algorithmes non récursifs (ils sont dit itératifs). Pour créer l'algorithme itératif à partir d'une définition récursive, il faut pouvoir stocker les résultats intermédiaires dans une variable :

algorithme puissance(x: entier, n: entier) → entier:
    r ← x
    c ← n - 1
    tant que c > 0:
        r ← r * x
        c ← c - 1
    rendre r

C'est cet algorithme itératif que nous allons étudier maintenant.

Est-ce que ça marche ?

On teste l'algorithme itératif sur de petits exemples qui vont nous permettre d'appréhender son fonctionnement :

Les cas simples que l'on peut essayer sans peine, et permet de tester les cas limites :

• n vaut 1
• x vaut 2 ou 3 (un peu plus que les cas triviaux)

Puis un cas un peu plus compliqué pour tester si les boucles fonctionnent bien :

• n vaut 2 ou 3
• x vaut 2 ou 3

Une fois qu'on est convaincu que ça fonctionne, on prouve sa finitude, son exactitude et on calcule sa complexité.

Preuve

En deux temps. On commence par montrer qu'il se termine, puis on prouve qu'il calcule bien l'exponentiation.

Finitude

• c est un entier qui diminue strictement à chaque boucle et la condition d'arrêt est lorsqu'il vaut 0.
• condition : il faut que c soit un nombre positif pour que l'algorithme s'arrête. Donc n doit être un nombre strictement positif.

Preuve de l'algorithme

Le fonctionnement de l'algorithme est à peu près clair si les entrées sont des entiers : il multiplie $a$ par lui-même $b$ fois grâce à une boucle. Une preuve par récurrence doit donc fonctionner, mais essayons de faire une jolie preuve en exhibant un invariant de boucle.

Prouvons cet invariant.

Juste avant la première itération de la boucle, r = x et c = n-1 notre invariant est donc vérifié. On suppose l'invariant vrai au début de la boucle $i$. Comme expliqué dans la partie sur les preuves d'algorithmes, on met un ' aux variable après l'itération :

• x' = x
• n' = n
• r' = r * x
• c' = c - 1

On a alors :

$$ r' \cdot {(x')}^{c'} = (r \cdot x) \cdot x^{c - 1} = r \cdot x^c = x^n = {(x')}^{n'} $$

On a démontré notre invariant de boucle.

Complexité de l'algorithme naif

Ligne à ligne :

1. une affection : $\mathcal{O}(1)$
2. une soustraction et une affection : $\mathcal{O}(1)$
3. une boucle de $\mathcal{O}(n)$ itération (c vaut initialement n et est décrémentée de $1$ à chaque itération)
4. une multiplication et une affection : $\mathcal{O}(1)$
5. une soustraction et une affection : $\mathcal{O}(1)$
6. retour de la fonction : $\mathcal{O}(1)$

Ce qui donne une complexité de :

Exponentiation indienne

Aussi appelé exponentiation rapide, cette façon de calculer l'exponentielle est basée sur l'équation suivante, pour deux entiers positifs $x$ et $n$ :

algorithme puissance(x: entier, n: entier) → entier:
    si n == 1:
        rendre x
    sinon si n % 2 ≠ 0:
        rendre x * puissance(x, n - 1)

    rendre puissance(x * x, n // 2)

Pour cette étude, nous allons uniquement utiliser des algorithmes itératifs. En procédant comme la partie précédente on obtient :

algorithme puissance(x: entier, n: entier) → entier:
    r ← x
    c ← n - 1

    tant que c > 0:
        si c % 2 == 1:
            r ← r * x
            c ← c - 1
        sinon:
            x ← x * x
            c ← c / 2

    rendre r

C'est cet algorithme itératif que nous allons étudier maintenant.

Est-ce que ça marche ?

Comme pour l'algorithme naïf, on vérifie que tout fonctionne avec les cas simples :

• n vaut 1 ou 2
• x vaut 2 ou 3 (un peu plus que les cas triviaux)

Enfin, comme l'algorithme vérifie si c est pair ou impair, on peut essayer un exposant un peu plus grand, par exemple :

• n = 7
• x = 2 (pas trop grand pour pouvoir calculer facilement les résultats de tête)

Preuve de finitude

De même que pour l'algorithme simple, c diminue strictement à chaque boucle (ou il diminue de -1 ou il est divisé par 2). Si n est un entier strictement positif en entrée, c reste entier après chaque boucle (on ne le divise par 2 que s'il est pair) et est strictement plus petit : l'algorithme va s'arrêter à un moment.

Preuve de l’algorithme

On va montrer que l'invariant de l'algorithme naïf fonctionne aussi. En notant X la valeur initial de x en entrée de l'algorithme, on a l'invariant suivant :

$$ r \cdot x^c = X^n $$

Juste avant la première itération de la boucle, $r = x$, $x = X$ et et $c = n-1$ notre invariant est donc vérifié au départ de l'algorithme. On suppose l'invariant vrai au début de la boucle d'itération $i$. Regardons comment les variables ont été modifiées lors de cette itération :

• si compteur est impair on a :
  • $c' = c - 1$
  • $r' = r \cdot x$
  • $x' = x$
  • l'invariant vaut alors en fin d'itération : $r \cdot x^c = (r \cdot x) \cdot x^{c - 1} = r' \cdot (x')^{c'}$
• si compteur est pair on a :
  • $c' = c / 2$
  • $r' = r$
  • $x' = x \cdot x$
  • l'invariant vaut alors en fin d'itération : $r \cdot x^c = r \cdot (x \cdot x)^{c/2} = r' \cdot (x')^{c'}$

Dans tous les cas, l'invariant est toujours vérifié puisqu'en début de boucle notre invariant vaut $r \cdot x^c = X^n$

Notre invariant est vrai avant et après chaque itération, il est donc également vrai à la fin de l'algorithme, lorsque $c = 0$, et là : $r \cdot x^c = r = X^n$

Complexité de l'exponentiation indienne

Pourquoi s'embêter avec la parité de compteur ? Parce que ça permet d'aller vachement plus vite !

On va le démontrer petit à petit, mais commençons par analyser ligne à ligne la complexité.

En notant $K$ le nombre de fois où l'on est rentré dans la boucle tant que de la ligne 4 on a une complexité ligne à ligne de :

1. une affectation : $\mathcal{O}(1)$
2. une affectation : $\mathcal{O}(1)$
3. —
4. une comparaison en $\mathcal{O}(1)$ et $K$ itérations de boucle
5. une opération de division entière et un test : $\mathcal{O}(1)$
6. une opération et une affectation : $\mathcal{O}(1)$
7. une opération et une affectation : $\mathcal{O}(1)$
8. —
9. une opération et une affectation : $\mathcal{O}(1)$
10. une opération et une affectation : $\mathcal{O}(1)$
11. —
12. un retour de fonction : $\mathcal{O}(1)$

Ce qui donne une complexité de :

La complexité est de l'ordre du nombre de fois où l'on rentre dans la boucle tant que : c'est à dire le nombre de fois où c a été modifié sans être égal à 0.

Nombre de fois où compteur est impair

Si à l'itération numéro $i$ compteur est impair, il sera pair à l'itération $i + 1$ car c' = c - 1 dans ce cas là.

On a donc que : le nombre d'itérations où compteur est impair est au pire égal au nombre de fois où il est pair

Nombre de fois où le compteur est pair

A chaque fois où compteur est pair, on le divise par 2. Si $K_p$ est le nombre de fois où le compteur a été pair, on a que : $2^{K_p} \leq n$.

Comme $n$ est un entier, il existe un nombre $p$ tel que $2^p \leq n < 2^{p + 1}$.

On ne peut donc pas diviser $n$ par 2, ou un nombre plus petit que lui, plus de $p$ fois. Ce nombre est exactement la partie entière de $\log_2(n)$. En effet :

On a donc que : le nombre d'itérations où c est pair est au pire égal à $\log_2(n)$

Nombre de fois où l'on rentre dans la boucle

Le nombre de fois où l'on rentre dans la boucle est égal au nombre de fois où le compteur est pair plus le nombre de fois où le compteur est impair, c'est donc au pire égal à deux fois le nombre de fois où compteur est pair, c'est à dire $2 \cdot \log_2(c)$ pour la valeur initiale de compteur.

Comme c vaut initialement n, le nombre de fois où l'on rentre dans la boucle est de l'ordre de $\mathcal{O}(\log_2(n))$ donc en $\mathcal{O}(\ln(n))$.

Comme les autres lignes sont en $\mathcal{O}(1)$ on a une complexité de l'algorithme en $\mathcal{O}(\ln(n))$.

Cette complexité est très faible ! Comparez par exemple : $2^{16} = 65536$ opérations et $\log_2(65536) = 16$ opérations.

Cette différence va aller exponentiellement lorsque compteur augmente, par exemple entre $2^{100} = 1267650600228229401496703205376$ et $100$ opérations

Complexité du problème

Peut-on faire mieux que l'exponentiation indienne pour calculer $x^n$ ? Remarquez que la complexité des algorithmes vus (itératif naïf et exponentiation indienne) dépendent exclusivement du nombre de multiplications utilisées :

• $n$ multiplications pour l'algorithme naïf itératif
• $\mathcal{O}(\log_2(n))$ multiplications pour l'algorithme de l'exponentiation indienne

On peut alors chercher à minimiser le nombre de multiplications de l'algorithme d'exponentiation :

Par exemple si $n=4$, on a besoin de 2 multiplications :

1. $x_1 = x \cdot x = x^2$
2. $x_2 = x_1 \cdot x_1 = x^4$

Et on a besoin de 4 multiplications si $n=10$ (on le prouve en vérifiant qu'il est impossible d'aller plus loin que $x^8$ en 3 multiplications) :

1. $x_1 = x \cdot x = x^2$
2. $x_2 = x_1 \cdot x_1 = x^4$
3. $x_3 = x_2 \cdot x_2 = x^8$
4. $x_4 = x_3 \cdot x_1 = x^{10}$

Avant de voir le cas général, allons un peu plus loin en comptant le nombre de multiplications utilisé par nos 2 algorithmes.

Le nombre de multiplications effectuées en utilisant l'exponentiation indienne est bien inférieure :

Ce n'est pourtant pas le nombre minimum :

L'exponentiation indienne n'a donc pas exactement le nombre minimum de multiplications possible !

Sous l'angle du nombre de multiplications, le calcul d'une exponentielle $x^n$ peut s'écrire comme :

Commençons par montrer que nos deux algorithmes peuvent s'écrire sous ce formalisme :

On peut maintenant montrer que toute suite multiplicative pour $x^n$ possède au moins $\log_2(n)$ éléments. On commence par remarquer et prouver par récurrence le résultat suivant :

Ceci permet de montrer que :

Ceci permet de dire que :

L'exponentiation indienne n'a donc certes pas le nombre minimum de multiplications, mais son ordre de grandeur est optimal !

Ceci nous permet d'écrire :

Terminons cette partie en montrant que la longueur minimale d'une suite multiplicative pour $x^n$ est toujours en $\mathcal{O}(\ln(n))$.

En notant $l(n)$ la taille minimale d'une suite calculant $x^n$, on a alors :

$$ \log_2(n) \leq l(n) \leq \lfloor\log_2(n)\rfloor + b(n-1) + 1 $$

Et donc, puisque $b(n-1) \leq \log_2(n)$ :

$$ \log_2(n) \leq l(n) \leq 2 \log_2(n) + 1 $$

L'encadrement ci-dessus est déjà très bon, il n'y a qu'un facteur 2 entre le minorant et le majorant. On peut même aller plus loin et montrer que $l(n) \sim \log_2 (n)$, nous ne ferons cependant pas la preuve ici (elle est longue et pas évidente du tout).

Conclusions

• la procédure utilisée pour l'étude de ces deux algorithmes est générale, vous pouvez (et devez) l'appliquer à l'étude de tout nouvel algorithme
• il ne faut jamais penser que l'on ne peut pas faire mieux pour un algorithme. Si vous ne connaissiez pas l'exponentiation indienne, il vous aurait été difficile de penser que l'on peut faire mieux que l'algorithme naïf pour calculer une exponentielle
• un informaticien ferait beaucoup de sacrifices pour obtenir une complexité en $\mathcal{O}(\ln(n))$ tellement c'est efficace
• on peut chercher la complexité minimale pour résoudre un problème et la comparer à des algorithmes connus.