UN ALGORITGHME EFFICACE DE CALCUL D'UNE PUISSANCE.
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 2016
-
15 mai 2005 à 14:04
pifou25
Messages postés144Date d'inscriptionlundi 13 octobre 2003StatutMembreDernière intervention21 décembre 2014
-
30 mars 2007 à 17:12
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
pifou25
Messages postés144Date d'inscriptionlundi 13 octobre 2003StatutMembreDernière intervention21 décembre 2014 30 mars 2007 à 17:12
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.
rambc
Messages postés224Date d'inscriptionmercredi 21 avril 2004StatutMembreDernière intervention29 mars 2009 24 mars 2006 à 00:01
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.
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 23 mars 2006 à 18:30
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.
rambc
Messages postés224Date d'inscriptionmercredi 21 avril 2004StatutMembreDernière intervention29 mars 2009 29 janv. 2006 à 13:19
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.
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 29 janv. 2006 à 12:20
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.
cs_algori
Messages postés868Date d'inscriptiondimanche 26 décembre 2004StatutMembreDernière intervention26 février 20081 29 janv. 2006 à 09:35
Cet algorithme s'appelle algorithme des PUISSANCES RAPIDES.
Ce qui veut tout dire.
@++
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 19 juin 2005 à 22:37
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.
ScSami
Messages postés1488Date d'inscriptionmercredi 5 février 2003StatutMembreDernière intervention 3 décembre 200724 18 mai 2005 à 01:30
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.
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 17 mai 2005 à 22:58
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.
rambc
Messages postés224Date d'inscriptionmercredi 21 avril 2004StatutMembreDernière intervention29 mars 2009 17 mai 2005 à 19:51
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 .
ScSami
Messages postés1488Date d'inscriptionmercredi 5 février 2003StatutMembreDernière intervention 3 décembre 200724 17 mai 2005 à 18:47
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és224Date d'inscriptionmercredi 21 avril 2004StatutMembreDernière intervention29 mars 2009 15 mai 2005 à 14:20
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.
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 15 mai 2005 à 14:04
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)...
30 mars 2007 à 17:12
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.
24 mars 2006 à 00:01
23 mars 2006 à 18:30
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.
29 janv. 2006 à 13:19
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.
29 janv. 2006 à 12:20
Amicalement,
Us.
29 janv. 2006 à 09:35
Ce qui veut tout dire.
@++
19 juin 2005 à 22:37
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.
18 mai 2005 à 01:30
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.
17 mai 2005 à 22:58
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.
17 mai 2005 à 19:51
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 .
17 mai 2005 à 18:47
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 :-)
15 mai 2005 à 14:20
15 mai 2005 à 14:04
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.