4 novembre 2011 5 04 /11 /novembre /2011 00:57

 

 

Lorsque l'on souhaite calculer an, on peut naïvement effectuer n-1 multiplications en faisant :

Cependant, l'exemple suivant montre que l'on peut calculer a2048 en effectuant simplement 11 multiplication (chaque fois que l'on élève au carré) :
L'algorithme d'exponentiation rapide est la transposition au cas général de l'exemple précédent. Une version récursive est donnée par :
  • si n=0, alors an=1.
  • si n=2p est pair, alors an=(ap)2.
  • si n=2p+1 est impair, alors an=(ap)2×a.
Alors que l'algorithme naïf demande de l'ordre de n multiplications pour calculer an, l'algorithme d'exponentiation rapide se contente de l'ordre de ln(n) multiplications. En outre, tester si un entier est pair est très rapide sur un ordinateur.

Partager cet article

commentaires

  • : Les Mathématiques Tchadiennes
  • Les Mathématiques Tchadiennes
  • : Blog dédié à l'Histoire, à la Beauté et à l'Enseignement des Mathématiques. Contact: ioms001@yahoo.fr
  • Contact


PLAQUEIBNI.jpg

"Le Professeur Ibni est un mathématicien tchadien de renom, Ancien Directeur du CNAR (CNRS tchadien), Ancien Recteur et Ancien Ministre de l'Enseignement Supérieur et de la Recherche, il avait initié plusieurs jumelages avec des Universités Etrangères, au service de l’enseignement des sciences dans son pays et en Afrique plus généralement"

PRIXIBNI.jpg
Candidature au Prix Ibni