UN ALGORITGHME EFFICACE DE CALCUL D'UNE PUISSANCE.

Signaler
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
-
Messages postés
144
Date d'inscription
lundi 13 octobre 2003
Statut
Membre
Dernière intervention
21 décembre 2014
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/31388-un-algoritghme-efficace-de-calcul-d-une-puissance

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.
Afficher les 13 commentaires