Un algoritghme efficace de calcul d'une puissance.

Commenter

Contenu du snippet

Voici un algorithme très efficace pour calculer une puissance entière (ce type d'alogrithme est utile pour des gros nombres bien entendus).

Source / Exemple : 


=====================================================
' Voir PAGE 8 de "A Course in Computational Algebraic
' Number Theory" de Henri COHEN.
' =====================================================
Puissance = X
Produit = 1
Expo = n

Do While Expo <> 0
    If Expo mod 2 = 1 Then Produit = Produit*Puissance

    Expo = Expo \ 2	

    If Expo <> 0 Then Puissance = Puissance*Puissance
Loop

' Voyons ce que fait l'algorithme sur un exemple.
'
' Calcul de 3^23. On commence donc avec  Puissance = 3
' et Expo = 23.
' Boucle N°1 : 	Expo = 23
'		Expo mod 2 = 1 donc Produit = 1*3 = 3
'              	Expo devient Expo \ 2 = 11
'              	Puissance = 3*3 = 3^2
' Boucle N°2 : 	Expo = 11
'		Expo mod 2 = 1 donc Produit = 3*3^2 = 3^3
'              	Expo devient Expo \ 2 = 5
'              	Puissance = 3^2*3^2 = 3^4
' Boucle N°3 : 	Expo = 5
'		Expo mod 2 = 1 donc Produit = 3^3*3^4 = 3^7
'              	Expo devient Expo \ 2 = 2
'              	Puissance = 3^4*3^4 = 3^8
' Boucle N°4 : 	Expo = 2
'		Expo mod 2 = 0 donc Produit = 3^7
'              	Expo devient Expo \ 2 = 1
'              	Puissance = 3^8*3^8 = 3^16
' Boucle N°4 : 	Expo = 1
'		Expo mod 2 = 1 donc Produit = 3^7*3^16 = 3^23
'              	Expo devient Expo \ 2 = 0
'
' Il a fallu faire 8 produits contre 23 avec une boucle du type 
' For i = 1 to Expo
' 	Produit = X*Produit
' Next
'
' De même, on pourrait vérifier que le calcul de 11^256 nous demanderait
' 9 = 8+1 produits contre 256=2^8 avec la méthode "naïve" ci-dessus.
'
' Maintenant si vous travaillez avec des  grands nombres ou des matrices
' et que votre multiplication s'appelle subFois alors on remplacera
' Produit = Produit*Puissance  par  Produit = subFois(Produit,Puissance)
' et Puissance = Puissance*Puissance  par  Puissance = subFois(Puissance,Puissance) .
'
' Si on travaille avec des matrices (ce qui est plus courant que
' d'utiliser des grands nombres), l'algorithme ci-dessus est un gain réel de temps
' (à vous de l'adapter et de tester) car il diminue le nombre de produits à calculer.
'
' En espérant avoir été plus clair et convaincant cette fois-ci.

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (rambc)