Étude : exponentiation

Cours/Algorithmie/Problème de l'exponentiation/É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 :

$$ x^n = \left\{ \begin{array}{ll} x \cdot x^{n-1} & \mbox{si } n > 1 \\ x & \mbox{sinon.} \end{array} \right. $$

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.

L'algorithme suivant, dérivant directement de la définition (donc correct) permet de calculer la puissance de deux nombres :

algorithme puissance(x: entier, n: entier) → entier:
    si n == 1:
        rendre x
    rendre x * puissance(x, n - 1)

Pour cette étude, nous allons uniquement utiliser des algorithmes itératifs. Commençons donc par transformer l'algorithme récursif en un algorithme itératif. Pour cela utilisons la récursion terminale. Commençons par l'écrire (comme on l'a fait pour la factorielle) sous la forme d'un algorithme récursif terminal, à l'aide d'un accumulateur (la paramètrer) :

fonction puissance_terminale(x: entier, n: entier, r: entier) → entier:
    si n == 1:
        rendre r
    rendre puissance_terminale(x, n - 1, x * r)

algorithme puissance(x: entier, n: entier) → entier:
    rendre puissance_terminale(x, n, x)

Ce permet d'écrire la version itérative par un simple jeu de réécriture :

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

Comme l'algorithme est issu d'une réécriture d'un algorithme récursif correct, il l'est forcément. Il ne nous reste donc plus qu'à calculer sa complexité.

Ligne à ligne :

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

Ce qui donne une complexité de :

$$ \begin{array}{lcl} C & = & \mathcal{O}(1) + \\ & & \mathcal{O}(1) + \\ & & \mathcal{O}(n) \cdot ( \\ & & \mathcal{O}(1) + \\ & & \mathcal{O}(1)) + \\ & & \mathcal{O}(1)\\ & = & 2 \cdot \mathcal{O}(1) + \mathcal{O}(n) \cdot (2 \cdot \mathcal{O}(1)) + \mathcal{O}(1)\\ &=& 3 \cdot \mathcal{O}(1) + 2 \cdot \mathcal{O}\mbox(1) \cdot \mathcal{O}\mbox(n)\\ &=& \mathcal{O}(3 \cdot 1) + \mathcal{O}\mbox(2\cdot 1 \cdot n)\\ &=& \mathcal{O}(3) + \mathcal{O}\mbox(2n)\\ &=& \mathcal{O}(1) + \mathcal{O}(n)\\ &=& \mathcal{O}(1 + n)\\ C&=& \mathcal{O}(n)\\ \end{array} $$

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$ :

$$ x^n = \left\{ \begin{array}{ll} x & \mbox{si } n = 1 \\ x \cdot x^{n-1} &\mbox{si } n > 1 \mbox{ est impair}\\ (x^2)^{(n/2)} &\mbox{si } n \mbox{ est pair}\\ \end{array} \right. $$

On propose l'algorithme itératif suivant pour résoudre le problème :

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

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

    rendre r

Est-ce que ça marche ?

Commençons par vérifier que l'algorithme fonctionne sur des 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)

Vérifiez que l'algorithme donne bien les bons résultats sur les exemples ci-dessus.

Preuve de finitude

La variable 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 boucle suivant fonctionne. En notant X la valeur initial de x en entrée de l'algorithme, on a le très élégant 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 :

une affectation : $\mathcal{O}(1)$
une affectation : $\mathcal{O}(1)$
—
une comparaison en $\mathcal{O}(1)$ et $K$ itérations de boucle
une opération de division entière et un test : $\mathcal{O}(1)$
une opération et une affectation : $\mathcal{O}(1)$
une opération et une affectation : $\mathcal{O}(1)$
—
une opération et une affectation : $\mathcal{O}(1)$
une opération et une affectation : $\mathcal{O}(1)$
—
un retour de fonction : $\mathcal{O}(1)$

Ce qui donne une complexité de :

$$ \begin{array}{lcll} C & = & \mathcal{O}(1) + &\\ & & \mathcal{O}(1) + &\\ & & K \cdot (\mathcal{O}(1) + &\\ & & \mathcal{O}(1) + &\\ & & \mathcal{O}(1) + &\mbox{(ligne 7 ou ligne 10)}\\ & & \mathcal{O}(1)) + & \mbox{(ligne 8 ou ligne 11)}\\ & & \mathcal{O}(1)&\\ &=& 2 \cdot \mathcal{O}(1) + K \cdot (5\cdot \mathcal{O}(1)) + \mathcal{O}(1)&\\ &=& 3 \cdot \mathcal{O}(1) + K \cdot 5 + &\\ C&=&\mathcal{O}(K)&\\ \end{array} $$

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 :

$$ \begin{array}{lcccl} 2^p &\leq &n &<& 2^{p + 1}\\ \log_2(2^p) &\leq &\log_2(n) &< &\log_2(2^{p + 1}) \mbox{ (car la fonction est croissante)} \\ p &\leq &\log_2(n) &<& p + 1 \end{array} $$

Pour tout nombre $x$, le nombre de fois où on peut diviser le diviser par $d$ est $\log_d(x)$

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

Cet exemple est traité dans le volume 2, partie 4.6.3, de The Art of Computer Programming de Knuth.

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 :

Question ?

Quel est le nombre minimum de multiplications nécessaires pour calculer $x^n = x \cdot \ldots \cdot x \cdot \ldots \cdot x$ à partir de $x$ ?

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

$x_1 = x \cdot x = x^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) :

$x_1 = x \cdot x = x^2$
$x_2 = x_1 \cdot x_1 = x^4$
$x_3 = x_2 \cdot x_2 = x^8$
$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.

Combien de multiplications sont nécessaires pour calculer $x^{15}$ si on utilisait l'exponentiation naïf ?

solution

On a besoin de 14 multiplications. Pour calculer $x^n$ ($n > 0$), on rentre $n-1 \geq 0$ fois dans la boucle.

$x_0 = x$
$x_1 = x \cdot x = x^2$
$x_2 = x_1 \cdot x = x^3$
...
$x_i = x_{i-1} \cdot x = x^{i+1}$
...
$x_{14} = x_{13} \cdot x = x^{15}$

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

Montrez que 6 multiplications sont nécessaires si on utilisait l'exponentiation indienne pour calculer $x^{15}$.

solution

L'algorithme de l'exponentiation indienne multiplie alternativement $r$ ou $x$ selon la parité de $c$. Pour calculer $x^{15}$ il procède ainsi :

$c = 15-1 = 14$ : une multiplication de $x$
$c = 14 / 2 = 7$ : une multiplication de $r$
$c = 7 - 1 = 6$ : une multiplication de $x$
$c = 6 / 2 = 3$ : une multiplication de $r$
$c = 3 - 1 = 2$ : une multiplication de $x$
$c = 2 /2 = 1$ : une multiplication de $r$
$c = 1 - 1 = 0$ : on ne fait plus de multiplications

On a eu besoin de 6 multiplications.

Ce n'est pourtant pas le nombre minimum :

Montrez que l'on peut calculer $x^{15}$ en uniquement 5 multiplications.

solution

$x_1 = x \cdot x = x^2$
$x_2 = x_1 \cdot x = x^3$
$x_3 = x_2 \cdot x_2 = x^6$
$x_4 = x_3 \cdot x_3 = x^{12}$
$x_5 = x_4 \cdot x_2 = x^{15}$

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 :

Définition

une suite multiplicative pour $x^n$ est une suite finie $(a_i)_{0\leq i \leq r}$ telle que :

$a_0 = x$
$a_r = x^n$
pour tout $i>0$, il existe $j$ et $k$ tels que $a_i = a_j \cdot a_k$ avec $0 \leq j \leq k < i$

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

Écrivez la forme de la suite multiplicative pour $x^n$ $(a_i)_{0\leq i \leq r}$ correspondant à l'algorithme d'exponentiation naïf.

solution

$a_0 = x$
$a_i = a_{i-1} \cdot a_0$ pour $0 < i \leq n-1$

Cette définition donne : $a_i = x^{i+1}$ et donc : $a_{n-1} = x^n$

Montrez que l'algorithme de l'exponentiation indienne peut s'écrire sous forme d'une suite multiplicative pour $x^n$ $(a_i)_{0\leq i \leq r}$ dont les premiers termes sont $a_i = x^{(2^i)}$ pour $i \leq \log_2(n)$.

solution

Les éléments de la suite correspondent aux valeurs successives de $r$. Cependant contrairement à l'exponentiation naïve qui change à chaque fois le résultat, l'exponentiation indienne change et le résultat et la valeur $x$. Pour être conforme à la définition (chaque élément de la suite dépend d'un élément précédent), il faut donc avoir à sa disposition les différentes valeurs de $x$ calculées par l'algorithme. Ces valeurs correspondent aux puissances $x^{2^i}$ pour $i=0$ à $i = \lfloor\log_2(n)\rfloor$ (partie entière (inférieure)).

Cette suite est bien multiplicative :

$a_0 = x$
$a_i = a_{i-1} \cdot a_{i-1}$ pour $1 \leq i \leq \log_2(n)$

Il nous reste ensuite à ajouter les éléments restant, c'est à dire tous les cas où le compteur est impair dans l'exécution de l'algorithme et qui correspondront à des $a_j = a_{j-1} \cdot a_i$ avec $1 \leq i \leq \log_2(n) \leq j$ qui correspondent au premier cas impairs de l'exécution de l'algorithme tel que $a_{j_0} = a_{i} \cdot a_{i'}$.

Cela donne la suite :

$a_0$
$a_1 = a_0 \cdot a_0$
$a_2 = a_1 \cdot a_1$
...
$a_i = a_{i-1} \cdot a_{i-1}$
$a_j = a_{0} \cdot a_{1}$ (premier impair)
$a_{j+1} = a_{j} \cdot a_{2}$
$a_{j+2} = a_{j+1} \cdot a_{3}$
...
$a_{m} = a_{m-1} \cdot a_{\log_2(n)}$

Que donne cette suite pour $n=15$ ? et pour $n=10$ ?

solution

Pour n=15 :

$a_0 = x$
$a_1 = a_0 \cdot a_0 = x^2$
$a_2 = a_1 \cdot a_1 = x^4$
$a_3 = a_2 \cdot a_2 = x^8$
$a_4 = a_0 \cdot a_1 = x^3$ (premier impair)
$a_5 = a_4 \cdot a_2 = x^7$
$a_6 = a_5 \cdot a_3 = x^{15}$

Pour n=10 :

$a_0 = x$
$a_1 = a_0 \cdot a_0 = x^2$
$a_2 = a_1 \cdot a_1 = x^4$
$a_3 = a_2 \cdot a_2 = x^8$
$a_4 = a_1 \cdot a_3 = x^{10}$ (premier impair)

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 :

Pour toute suite multiplicative $(a_i)_{0\leq i \leq r}$ pour $x^n$, on a toujours : $a_i \leq x^{2^i}$ (avec $2^0 = 1$)

solution

On le montre par récurrence.

C'est vrai pour $i=0$ puisque $a_0 = x =x^{2^0}$. On suppose la propriété vraie pour tout $j \leq i$ et on considère $i+1$. On a $a_{i+1} = a_j \cdot a_k$. Comme $k \leq j \leq i$, l'hypothèse de récurrence est satisfaite pour $a_j$ et $a_k$, donc : $a_{i+1} = a_j \cdot a_k \leq x^{2^j} \cdot x^{2^k} \leq x^{2^{i}} \cdot x^{2^{i}} = x^{2^{i+1}}$. Ce qui conclut la récurrence.

Ceci permet de montrer que :

Proposition

Toute suite multiplicative pour $x^n$ $(a_i)_{0\leq i \leq r}$ est telle que :

$$ \log_2(n) \leq r $$

preuve

Comme $a_r = x^n$, on a $n \leq 2^r$ ce qui donne, en passant au log : $\log_2(n) \leq r$.

Ceci permet de dire que :

Proposition

Tout algorithme calculant l'exponentielle $x^n$ est en $\Omega(\ln(n))$

preuve

Il faut toujours au moins $\log_2(n)$ multiplications donc la complexité est forcément supérieure à ce nombre.

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 :

Proposition

La complexité du problème de l'exponentiation est en $\Theta(\log_2 (n))$.

preuve

Comme la complexité de l'algorithme de l'exponentiation indienne est en $\mathcal{O}(\ln(n))$, la proposition précédente permet de conclure.

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

En remarquant que si $b = b_0\dots b_k$ est la représentation binaire d'un nombre alors la représentation binaire de $b/2$ est $b / 2 = b_1\dots b_k$, déduire que le nombre de fois où le compteur est impair dans l'algorithme de l'exponentiation indienne est égal au nombre de 1 de la représentation binaire de $n-1$, noté $b(n-1)$.

solution

Un nombre est impair si le premier bit de sa représentation binaire vaut 1. Le nombre $b // 2^i$ est impair si $b_i = 1$.

On conclut la preuve en remarquant que tout au long de l'algorithme, le compteur c vaut soit :

$b // 2^i$ si ce nombre est pair
$b // 2^i - 1$ sinon

En déduire que la longueur de la suite pour l'exponentiation indienne est :

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

Avec $\lfloor x\rfloor$ la partie entière inférieure de $x$ et $b(x)$ le nombre de bits à 1 de la représentation binaire de $x$.

solution

Les premiers éléments de la suite sont au nombre de $\lfloor\log_2(n)\rfloor + 1$ (les $a_i = x^{2^i}$ tant que $a_i < x^n$), les derniers éléments étant ajoutés à chaque fois que le compteur est impair.

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.