Retour à la page précédente

Puissances

Soit n ≥ 1 un entier. On veut calculer aⁿ .
La méthode classique nécessite (n-1) multiplications. Voici un algorithme plus efficace.

A := a;
N := n;
R := 1;
tant que N > 0 faire
si N pair alors début A := A * A; N := N/2; fin
sinon début R := R * A; N := N − 1; fin.

1. Est ce que vous êtes convaincu que cet algorithme calcule bien aⁿ (plus précisément qu'en sortie R contient aⁿ ) ?
   Si les essais que vous avez faits ne vous ont pas convaincu, alors voici comment prouver l'algorithme.
   
   Montrez que A ^N x R = aⁿ est un invariant de la boucle : c'est à dire que si l'égalité est vérifiée en entrée de boucle, alors elle reste vraie en sortie de boucle. Solution
   Reste à voir qu'elle était vraie avant d'entrer dans la boucle, ce qui est évident : Aⁿ x 1 = aⁿ.
   La conclusion est qu'elle est vraie lorsque la boucle est terminée, c'est à dire que A⁰ x R = aⁿ cqfd.
   
   
2. Combien de multiplications sont nécessaires cette fois ? Indication1
   
   
3. Pouvez vous trouver un algorithme qui fasse mieux ?