10
votes

Quel est l'algorithme le plus rapide pour effectuer l'exponentiation?

Quel est l'algorithme le plus rapide pour effectuer l'exponentiation? Supposons les bases de nombre naturel et les exposants de la simplicité.

Quelle serait une bibliothèque de mathématiques efficace?

(Lorsque je le cherche, je viens d'obtenir des résultats relatifs aux algorithmes qui fonctionnent dans une période exponentielle.)


4 commentaires

JOHNDCOOK.COM/BLOG/2008/12/10/FAST-Exponiation


Je pense que cela a demandé à cent fois.


Qu'entendez-vous par «Exposant d'un numéro»?


Knuth a consacré plusieurs pages de TAOCP Volume 2 dans ce problème.


3 Réponses :


2
votes

Pour les petits exposants Python utilise une exponenciation binaire (type d'exponentiation par quart), comme on peut le voir à la ligne 2874 de http://svn.python.org/view/python/trunk/Objects/longObject.c?view=markup&pathrev=65518

Pour les plus grands exposants, il utilise une exponentiation de 2 ^ 5-ary (un type alternatif d'exponentiation par querelle).

Si vous ne vous souciez que des chiffres les plus significatifs du résultat, vous pouvez alors calculer très rapidement x ^ y = exp (Y * journal (x)).

Si vous ne vous souciez que des chiffres les moins importants du résultat (par exemple pour un concours de programmation), vous pouvez calculer l'exposant modulo une certaine valeur M. Par exemple, la commande Python POW (X, Y, 1000) sera calculée les 3 derniers chiffres de X à la puissance de y. Cela fait ceci par l'exponentiation par la méthode de querelle, mais noter que cela peut être beaucoup plus rapide que celui de calculer le résultat complet, car il veille à ce que les numéros intermédiaires ne soient jamais plus grands que m.

En tant que torsion supplémentaire (si vous n'êtes intéressé que par les chiffres les moins importants), vous pouvez utiliser le théorème d'Euler http://en.wikipedia.org/wiki/euler%27s_theorem pour réduire la taille de l'exposant.


1 commentaires

Ce lien Svn.python.org n'est plus bon; Je pense que c'est le code pertinent (maintenant sur github) cependant: github.com/pythron/cpython/blob/master/Objects/.../a>



0
votes

Si vous avez un numéro naturel donné, U et une entrée donnée m, vous pouvez appliquer l'algorithme suivant

q = m;
prod = 1;
current = u;
while q > 0 do
     if (q mod 2) = 1 then // detects the 1s in the binary expression of m
          prod = current * prod; // picks up the relevant power
          q--;
     endif
current = current * current; // u^i -> u^(2*i)
q = q div 2
enddo

output = prod;


1 commentaires

Cette analyse ne concerne pas l'heure de fonctionnement de la multiplication.



4
votes

Le problème de toutes les méthodes binaires ci-dessus est qu'ils sont limités aux entiers uniquement. Si par "Exponciation", vous voulez dire calculer la fonction E ^ x, le meilleur que j'ai vu est la série de puissances qui convergent rapidement et les approximations polynomiales, rationnelles ou pales valides sur une plage limitée.

Une chose à coup sûr: si vous trouvez un algorithme rapide de la foudre pour des décimales E ^ x à 96, vous aurez également trouvé un moyen plus rapide de calculer des grumes (de Newton-Raphson). En fait, Newton-Raphson converge quadratique, de sorte que vous doublez le nombre de chiffres de précision dans votre journal avec chaque itération. C'était un favori de Nate Grossman de UCLA de retour dans les jours.

Retour dans les jours des calculatrices de quatre pandes, j'avais l'habitude d'utiliser E ^ x = (1 + x / 1024) ^ 10. Bien sûr, cela tombe sur X très grand ou très petit, mais vous pouvez voir pourquoi cela fonctionne. Si vous avez un bouton racine carré, vous pouvez inverser cette idée pour obtenir des logarithmes. Mais vous n'avez pas besoin de racine carrée pour la fonction exponentielle.

Je me demande s'il y a une inversion de l'algorithme AGM qui pourrait faire la fonction exponentielle ... Hmmm ....


0 commentaires