Exercice 1 — Exponentiation rapide

Sujet

On s'intéresse dans cet exercice au calcul de \(a^{n}\), où \(a\) est un nombre réel et \(n\) un entier naturel non nul. On rappelle que \(a^{n}=a \times a \times a \times \cdots \times a\) avec \(n\) facteurs.

1. Combien de multiplications sont a priori nécessaires pour calculer \(a^{n}\) ?
2. Proposer un algorithme qui permette de calculer \(a^{n}\).

On souhaite maintenant optimiser le calcul de \(a^{n}\) c'est-à-dire calculer \(a^{n}\) avec le moins de multiplications possibles.
Ainsi par exemple, pour calculer \(a^{4}\), on peut calculer \(b=a \times a\) (une multiplication) puis \(a^{4}=b \times b\) (une multiplication). On calcule de cette façon \(a^{4}\) avec deux multiplications seulement.
3. a) Montrer que l'on peut calculer \(a^{8}\) avec trois multiplications seulement.
b) Montrer que l'on peut calculer \(a^{10}\) avec quatre multiplications seulement et de deux façons différentes.
4. On propose l'algorithme suivant pour effectuer le calcul de \(a^{n}\) :

\(R\) prend la valeur 1
\(N\) prend la valeur \(n\)
\(A\) prend la valeur \(a\)
Tant que ( \(N>0\) ) faire
Si ( \(N\) est impair) Alors
\(R\) prend la valeur \(R \times A\)
Fin Si
\(N\) prend la valeur égale au quotient de la division euclidienne de \(N\) par2
\(A\) prend la valeur \(A \times A\)
Fin Tant que
Afficher \(R\)
a) On programme l'algorithme ci-dessus et on l'exécute pour le calcul de \(3^{12}(a=3, n=12)\).

Recopier et compléter le tableau d'évolution des variables ci-dessous :

b) Calculer pour chaque ligne du tableau la quantité \(A^{N} \times R\). Qu'observe-t-on ?

Cette quantité est l'invariant de la boucle; il permet de montrer dans le cas général que cet algorithme effectue bien le calcul de \(a^{n}\).
c) Combien de multiplications ont été effectuées pour le calcul de \(3^{12}\) par cet algorithme?
d) Combien de multiplications seraient effectuées pour le calcul de \(a^{2015}\) par cet algorithme?