Quel est le nombre minimal de multiplications pour calculer xⁿ dans chaque cas suivant :

Explications (Inspiré de Donald Knuth The Art of Computer Programming)

Il y a deux méthodes classiques (on suppose quon peut garder en mémoire les résultats intermédiaires obtenus et donc les réutiliser sans les recalculer).

Ecrivez n en base 2, puis remplacez dans lécriture trouvée chaque 1 par SX, chaque 0 par S. Supprimez le SX qui apparaît à gauche.

Interprétez lécriture obtenue comme le moyen de calculer x ⁿ : S désigne la mise au carré et X la multiplication par x.

Par exemple 15 = 1111 en binaire donne SXSXSXSX ce qui sinterprète (à condition de commencer par la droite) comme :

x ¹⁵ = X(S(X(S(X(S(x)))))) soit x * (x * (x * x ² ) ² ) ²

Donc pour 15, la méthode binaire nécessite 6 multiplications b(15) = 6.

Elle consiste à utiliser une factorisation de n : n = p q où p est le plus petit facteur premier de n et q > 1. On calcule dabord x ^p quon élève ensuite à la puissance q.

Par exemple, pour x ¹⁵ on calcule x ³ en deux multiplications, puis on élève x ³ à la puissance 5 en trois multiplications, y ⁵ = y * (y ² ) ²

Donc, par la méthode de factorisation, on calcule x ¹⁵ en 5 multiplications : f(15) = 5.

• Pour 16 la méthode binaire est la meilleure : (((x ²)² ) ²)²
• Pour 15, la méthode binaire nécessite 6 multiplications b(15) = 6, alors que par la méthode de factorisation, on calcule x ¹⁵ en 5 multiplications .
• 23 est le plus petit exemple où la meilleure méthode nest ni la méthode binaire, ni la méthode par factorisation : b(23) = 7, f(23) = 1 + b(22) = 7
  tandis quon peut calculer x ²³ en 6 multiplications : on calcule x ³ en deux multiplications : x ² * x puis x ⁵ en une multiplication supplémentaire x ³ * x² et x ¹⁰ comme carré de x ⁵ et enfin x ²³ =( x ¹⁰ * x ³ ) * x ¹⁰
• Pour 33 la méthode binaire est la meilleure b(33) = 6, f(33) = 7
• Pour 55 la méthode par factorisation est la meilleure b(55) =9 , f(55) = 8