Visual Basic, VB6, VB.NET, VB 2005, VB CodeS-SourceS

CodeS-SourceS est hébergé par Frontier.fr

Cliquez ici pour mettre ce site au démarrage de votre navigateur

AccueilCodesTutorielsForumsEmploiLivresConnexion

begin process at 2008 12 05 17:08:56

[SILVERLIGHT] SILVERLIGHT ET L'AFFICHAGE DE CODE HTML par Thomas LEBRUN

AVEC SOFTWEAR, MICROSOFT LANCE SA LIGNE DE VêTEMENTS... par Yannick

[OPENXML4J] THE FUTURE OF OPENXML4J par neodante

[OPENXML4J] UTILISER OPENXML4J OU POI POUR SES PROJETS JAVA AVEC OPEN XML : L'AVENIR DU PROJET OPENXML4J par neodante

LA NOTION DE CLASSE ABSTRAITE EN PHP5 par orion

RE : PROBLEME: DONNéES TéLéCHARGéES VIA UNE MACRO SONT AU FORMAT NOMBRE US par jay18

RE : CRéE AUTOMATIQUEMENT UN TEXTBOX par meldur74

RE : CRéE AUTOMATIQUEMENT UN TEXTBOX par NHenry

RE : DOUBLON TABLEAUX par NHenry

RE : SELECTFOLDER ... par Sator

+ de logiciels à télécharger

1 304 301 membres
454 nouveaux aujourd'hui
14 559 membres club

Trouver une ressource

Trouvez une ressource parmi 39 093 codes, 1 209 762 messages d'aide etc...

Recherche: dans [ Dernières recherches ]

Filtre:Tous les codes.NET uniquementExclure .NET

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

UN ALGORITGHME EFFICACE DE CALCUL D'UNE PUISSANCE.

Information sur la source

Catégorie :Maths Niveau : Débutant Date de création : 15/05/2005 Date de mise à jour : 17/05/2005 21:27:27 Vu : 9 661

Auteur : rambc

Ecrire un message privé

Note :

10,00 / 10

Commentaire sur cette source (13)

Ajouter un commentaire et/ou une note

Description

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

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

Historique

17 mai 2005 21:27:27 :: Explications via un exemple.

Sources du même auteur

OUTLOOK MAIL(SUJET ET MESSAGE) / OUVRIR UNE PAGE NET (VÉRIFI...

VBA-WORD TESTER ET ACTUALISER UN CHEMIN D'ACCÈS À UN FICHIE...

Toutes les sources de rambc

Sources de la même categorie

ANALYSE SPECTRALE SOUS EXCEL (TFR OU FFT) par Patrice99

RÉSOLUTION DE L'ÉQUATION DE LA CHALEUR par Arnal88

CALCULETTE POUR PROGRAMMEUR par Galactus13

OPERATIONS MATRICIELLES par yass21

CONVERTIR DÉC-BIN-OCT-HEX par titpeanut

Toutes les sources de la catégorie Maths

Commentaires et avis

Commentaire de us_30 le 15/05/2005 14:04:47

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.

Commentaire de rambc le 15/05/2005 14:20:54

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.

Commentaire de ScSami le 17/05/2005 18:47:52

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 :-)

Commentaire de rambc le 17/05/2005 19:51:55

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 .

Commentaire de us_30 le 17/05/2005 22:58:28

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.

Commentaire de ScSami le 18/05/2005 01:30:22

Je suis d'accord avec US30... Ce serait vraiment bien si tu pouvais nous mettre tes macros online...

Je tiens cependant à m'excuser pour mes précédents propos... En effet, ce n'est pas inutile (tout du moins, sous cette nouvelle forme :-).

Non, franchement, avec tes nouvelles explications, je suis convaincu et je n'hésite pas à te mettre 10/10 pour cette technique, me semble-t-il, inédite sur CS.

Pardon de t'avoir vexé si c'était le cas.

Respect.

Commentaire de us_30 le 19/06/2005 22:37:50

Salut,

JE reviens bien plus tard pour te mettre également à mon tour un 10/10... Car en définitive, ton algorithme est vraiment super utile, et me semble même optimale dans son genre... JE viens de m'en servir pour la programmation des puissances avec les grands nombres... et franchement c'est du tonnerre !
Tu as très bien fait de le mettre en ligne, et je t'en suis reconnaissant...

Auparavant, j'ai déjà lu quelqu'uns de tes propos sur d'autres posts... et il me semble que tu te penches sur la programmation des grands nombres de manière sérieuse, et avec succès, chose qui m'occupe également... je suis très intéressé de connaître ton avis sur les quelques opérations que j'ai déjà posté sur le sujet... et je suis encore plus intéressé de connaître tes macros qui tu as programmées, afin d'en apprendre davantage...

Amicalement,
Us.

Commentaire de algori le 29/01/2006 09:35:29

Cet algorithme s'appelle algorithme des PUISSANCES RAPIDES.
Ce qui veut tout dire.
@++

Commentaire de us_30 le 29/01/2006 12:20:38

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.

Commentaire de rambc le 29/01/2006 13:19:45

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.

Commentaire de us_30 le 23/03/2006 18:30:26

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.

Commentaire de rambc le 24/03/2006 00:01:00

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.

Commentaire de pifou25 le 30/03/2007 17:12:21

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.