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