Retour à la page précédente

Puissances

Soit n ≥ 1 un entier. On veut calculer an .
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 an (plus précisément qu'en sortie R contient an ) ?
    Si les essais que vous avez faits ne vous ont pas convaincu, alors voici comment prouver l'algorithme.

    Montrez que A N x R = an 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 : An x 1 = an.
    La conclusion est qu'elle est vraie lorsque la boucle est terminée, c'est à dire que A0 x R = an cqfd.

  2. Combien de multiplications sont nécessaires cette fois ? Indication1

  3. Pouvez vous trouver un algorithme qui fasse mieux ?