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.
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.