Avancer

Section 3.2 Exponentiation rapide

Comment utiliser efficacement l'ordinateur pour calculer la puissance \(n\)-ième d'un nombre réel \(x\text{,}\) c'est-à-dire \(\displaystyle x^n\text{?}\)

Algorithme 1 : Approche naïve.

Combien de multiplications doit-on effectuer pour évaluer \(5^7\text{?}\)

On a

\begin{equation*} 5^7=5\cdot 5\cdot 5\cdot 5\cdot 5\cdot 5\cdot 5, \end{equation*}

et vu comme ça, il en faut six.

Plus généralement, on a besoin de \(n-1\) multiplications pour évaluer

\begin{equation*} x^n=x\cdot x\cdot x\cdots x. \end{equation*}

Voici une implémentation de l'algorithme qui renvoie la valeur de \(x^n\) en suivant cette approche naïve.

Si on ne tient compte que des opérations mathématiques, la complexité en temps de cet algorithme ne dépend que de l'entrée \(n\) et vaut

\begin{equation*} T(n)=n-1. \end{equation*}

On parle donc de complexité linéaire.

Algorithme 2 : Exponentiation rapide.

Revenons au calcul de \(5^7\) et notons que

\begin{equation*} 5^7=5\cdot 5^2\cdot 5^4 \end{equation*}

où

\begin{equation*} 5^2=5\cdot 5\quad\text{avec}\quad 5^4=5^2\cdot 5^2. \end{equation*}

Vu comme ça, le calcul de \(5^7\) ne requiert plus que quatre multiplications.

Cet exemple nous conduit à adopter une approche récursive basée sur la disjonction de cas suivante :

\begin{equation*} x^n= \begin{cases} x&\text{ si }n=1,\\ \left(x^2\right)^{n/2}&\text{ si }n\text{ est pair,}\\ x\cdot\left(x^2\right)^{(n-1)/2}&\text{ si }n\geq 3\text{ est impair.} \end{cases} \end{equation*}

Voici une implémentation de cette approche, où la fonction puissanceRecursive(x, n) renvoie la valeur de \(\text{x}^\text{n}\) de manière récursive.

Si on ne tient compte que des multiplications, une analyse basée sur l'écriture en binaire de \(n\) permet de montrer que la complexité \(T(n)\) de cet algorithme vérifie l'encadrement

\begin{equation*} \log_2(n)-1\leq T(n)\leq 2\log_2(n). \end{equation*}

On a donc une complexité logarithmique, qui est bien meilleure que la complexité linéaire de l'approche naïve, comme l'illustrent les graphes ci-après.

Figure 3.2.2. Linéaire vs logarithmique