Un algoritghme efficace de calcul d'une puissance.

Soyez le premier à donner votre avis sur cette source.

Snippet vu 20 811 fois - Téléchargée 30 fois

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

Ajouter un commentaire

Commentaires

Messages postés
144
Date d'inscription
lundi 13 octobre 2003
Statut
Membre
Dernière intervention
21 décembre 2014

super! énorme! je cherchais justement un algo efficace pour mes gros nombres, mais en 3 lignes, vraiment formidable :)
J'ai fais des structures BigInt donc pas besoin de fonctions subFois pour mes grands nombres mais j'avais besoin de surcharger l'opérateur d'exposant pour mes bigInt. Je mettrais à jour la source actuelle avec ce code ^^ je poste les sources mais il est possible d'en faire une DLL. Par contre moi je l'ai codé en .NET pour pouvoir manipuler les grands nombres comme des int ou des double.
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009

UN GRAND MERCI pour toutes ces astuces de pure programmation. Etant un auto-didacte total, je passe à côté de choses techniques comme celles indiquées qui me convaiquent pleinement.
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
8
Bonjour,

Encore un petit mot sur l'algorithme, en terme d'optimisation.

Même si ce que tu proposes est juste, on peut encore l'optimiiser sur quelques points.

1. Le premier est plus une astuce de programmation. La condition " Expo mod 2 = 1 " sert uniquement à savoir si Expo est impair. IL est plus rapide d'utiliser le test du dernier bit sur Expo, grâce à " Expo And 1"

2. La boucle DO WHILE... LOOP est moins rapide que DO... LOOP WHILE. C'est encore un pur pb informatique...

3. Le test " Expo <> 0 " regarde si Expo est négatif. Or, l'algo ne peut pas fonctionner dans ce cas. Donc seul " Expo > 0" est utile. Mais, on peut encore faire mieux...

4. Le test " If Expo <> 0 Then " n'est utile qu'à la fin. Plus précisement lorsque Expo = 0, afin d'éviter le dernier calcul qui serait inutile. Or, il est à noter que Expo passera toujours par 1, puis 0. IL est donc possible d'éviter de mettre le test dans la boucle, en arrêtant la boucle à 1, puis en faisant le dernier calcul en dehors de DO. A cela seul les deux cas particulier Expo=0 et Expo=1 doivent être traités séparément. Mais cela demande uniquement 2 tests, au lieu d'une série dans la boucle DO...

=

VOICI la version algorithmique totalement optimisé que je te propose :


'--ALGO TOTALEMENT OPTIMISE--

Puissance = X
Produit = 1
Expo = n

If Expo 0 Then Produit 1: Exit Function
If Expo 1 Then Produit Puissance: Exit Function

Do
If Expo And 1 Then Produit = Produit * Puissance
Expo = Expo \ 2
Puissance = Puissance * Puissance
Loop While Expo > 1

Produit = Produit * Puissance

---

Aucun calcul ou test n'est exécuté plus que nécessaire.

Amicalement,
Us.
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009

De rien, cela ne me coûte rien dans la mesure où je travaille (entre autres choses) sur un projet de calculatrice en précision infinie. Je posterais peut-être d'autres algorithmes : je pense notamment à des méthodes efficaces pour calculer des séries entières comme celle de EXP X = 1 + X + X^2/2! + X^3/3! + ... (Binary Splitting pour ceux qui connaissent).
Je voulais poster des sources pour calculer efficacement une division euclidienne ou un produit de deux entiers (de tailles quelconques) mais ce type de source relève plus des mathématiques que de la programmation (donc je pense que j'aurais perdu pas mal de personnes au passage et ce n'est pas le but de ce type de site).

PS : Si quelqu'un sait comment fabriquer une DLL, je suis preneur car je voudrais faire de mes modules de calculs VB-VBA, des DLL pour gagner en rapidité de calculs.
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
8
Oui, et depuis j'ai trouvé quelques documents mathématiques qui le décrit. Reste que je ne l'ai jamais trouvé écrit en VB... donc encore merci Rambc...

Amicalement,
Us.
Afficher les 13 commentaires

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.