Un algoritghme efficace de calcul d'une puissance.

Soyez le premier à donner votre avis sur cette source.

Snippet vu 20 575 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

us_30
Messages postés
2117
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
7 -
Salut,

Euh...bon...je voudrais pas décevoir... mais si on veut la puissance 23 d'un nombre on fait X^23 jusqu'à maintenant ? A quoi sert donc ton algorithme ? d'autant qu'il calcul par défaut en Variant donc avec la même précision que Double... je veux dire par là, que le calcul n'est pas en multiprécision (affichage avec une String)...

Enfin, bon...

Us.
rambc
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009
-
Vous avez raison mais je donne juste l'algorithme qui m'est d'une grande utilité pour calculer sur des grands nombres. Le titre parle d'algorithme et non de module de calcul. De plus dans mon commentaire j'indique bien qu'il ne sert que pour des grands nombres (ce que ne sont pas les variant). Pour la méthode générale, il aurait fallu que j'intègre mes modules de calculs sur des grands nombres et là il faudrait un zip : le problème est que les procédures que j'ai faite sont pour des macros Word.
ScSami
Messages postés
1488
Date d'inscription
mercredi 5 février 2003
Statut
Membre
Dernière intervention
3 décembre 2007
17 -
Hum... C'est vrai que c'est complétement inutile!!!
De plus, on ne comprends pas très bien les explications (oops, désolé, le code n'est pas commenté!!!).
Le problème de ton algo là, c'est qu'il ne sert pas vraiment pour les grands nombres!!! Alors peut-être n'avons-nous pas la même notion de "grand nombres"!?!? J'entends par "grands nombres" ceux qui contiennent plusieurs milliers voire centaine de milliers de chiffres... Or, dans ce cas ton algo serait totalement inefficace (puisque, en effet, il n'utilise pas de String) et qui plus est, très lent face à d'autres (que je finirais par déposer sur VBF quand j'en aurais le temps vu la récurrence de ces sujets [calcul de grands nombres]).

De plus, je ne vois vraiment pas où se trouve le problème, tant du zip que de la diffusion de procédures Word qui, je l'espère, sont plus complètes !!!

Bref, là, je reste perplexe!

Ceci dit, certes, l'idée est plus originale que :
For T=1 to Puissance
Resultat = Resultat * X
Next T

Merci quand même de nous avoir fait partager cette méthode :-)
rambc
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009
-
UNE FOIS POUR TOUTE (je dis cela sans agressivité), un algorithme n'est pas une procédure. Cet algorithme S'ADAPTE à plein de situations : pour multiplier des matrices, il suffit de reprendre chaque ligne et d'adapter.

Côté explications : l'exemple est suffisant me semble-t-il.

Côté grand nombre, j'indique les modestes performances de mes procédures qui fonctionnent avec des STRING.
1) Calcul du produit de deux entiers de 5 000 chiffres en environ 3 min 30 s.
2) Calcul de 115^2599 en environ 64 secondes.
3) Division d'un naturel de 2000 chiffres par un naturel de 10 chiffres en environ 0,3 s .
us_30
Messages postés
2117
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
7 -
Re-Salut,

Je partage assez volontier les remarques de ScSami, sans aller toutefois à dire que cela est inutile... Parfois une idée permet d'ouvrir l'esprit sur d'autres idées. D'ailleurs, lorsque je cherche, j'ai tendance à cumuler les idées inutiles, pour arriver au but. Preuve qu'elles doivent être finalement utiles, même si elles ne me servent pas... c'est un peu paradoxale, je sais...

Mais, ma nouvelle intervention n'est pas philosophique. JE suis intéressé justement par des algorithmes pour calculer sur des grands nombres. J'y réfléchi un peu. D'ailleurs, ce n'est pas un sujet vraiment trés bien traité sur VBF et ailleurs. Du moins, j'en n'ai pas trouvé qui me satisface complètement. Seul, le post http://www.vbfrance.com/code.aspx?id=7338 me semble un bon début... enfin il me semble... Enfin, bref... tout ça pour demander (à Rambc) si les Macros de calcul sous Word pouvait être mise en ligne... et bien... je serais un des premiers lecteurs... tout comme pour ScSami, s'il se lance dans ce projet...


Amicalement,
Us.

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.