Comment les exposants sont-ils calculés?

Question

J'essaie de déterminer le temps d'exécution asymptotique d'un de mes algorithmes, qui utilise des exposants, mais je ne suis pas sûr de la façon dont les exposants sont calculés par programme.

Je recherche spécifiquement l'algorithme pow () utilisé pour les nombres en virgule flottante double précision.

Answer 1

J'ai eu l'occasion d'examiner la mise en œuvre de fdlibm. Les commentaires décrivent l'algorithme utilisé:

 *                    n
 * Method:  Let x =  2   * (1+f)
 *      1. Compute and return log2(x) in two pieces:
 *              log2(x) = w1 + w2,
 *         where w1 has 53-24 = 29 bit trailing zeros.
 *      2. Perform y*log2(x) = n+y' by simulating muti-precision
 *         arithmetic, where |y'|<=0.5.
 *      3. Return x**y = 2**n*exp(y'*log2)

suivi d'une liste de tous les cas spéciaux traités (0, 1, inf, nan).

Les sections les plus intenses du code, après toute la gestion des cas spéciaux, impliquent les calculs log2 et 2 ** . Et il n'y a pas de boucles dans ces deux cas. Ainsi, malgré la complexité des primitives à virgule flottante, cela ressemble à un algorithme asymptotiquement constant.

Les experts en virgule flottante (dont je ne fais pas partie) sont invités à commenter. : -)

Answer 2

À moins qu’ils n’aient découvert un meilleur moyen de le faire, j’estime que les valeurs approximatives des fonctions trigonométriques, logarithmiques et exponentielles (pour la croissance et la décroissance exponentielles, par exemple) sont généralement calculées à l’aide de règles arithmétiques et de Taylor Series extensions pour produire un résultat approximatif avec une précision correspondant à la précision demandée. (Voir un livre de calcul pour plus de détails sur les extensions de fonctions de la série power, de la série Taylor et de la série Maclaurin.) Veuillez noter que cela fait longtemps que je n’ai fait aucune de ces opérations, je ne saurais donc pas vous dire exactement comment calculer. le nombre de termes de la série à inclure garantit une erreur suffisamment petite pour être négligeable dans un calcul à double précision.

Par exemple, l’extension de la série Taylor / Maclaurin pour e ^ x est la suivante:

      +inf [ x^k ]           x^2    x^3      x^4        x^5
e^x = SUM  [ --- ] = 1 + x + --- + ----- + ------- + --------- + ....
      k=0  [  k! ]           2*1   3*2*1   4*3*2*1   5*4*3*2*1

Si vous prenez tous les termes (k de 0 à l'infini), cette extension est exacte et complète (pas d'erreur).

Cependant, si vous ne prenez pas tous les termes à l'infini, mais si vous vous arrêtez après 5 ou 50 termes, vous obtenez un résultat approximatif différent du e réel ^. x valeur de la fonction par un reste assez facile à calculer.

La bonne nouvelle pour les exponentielles est qu’elle converge bien et que les termes de son expansion polynomiale sont assez faciles à coder de manière itérative, de sorte que vous pourriez (répéter, PEUT ) Cela fait un moment que vous n’avez même pas besoin de pré-calculer le nombre de termes dont vous avez besoin pour garantir que votre erreur est inférieure à la précision, car vous pouvez tester la taille de la contribution à chaque itération et vous arrêter quand elle devient assez proche de zéro. En pratique, je ne sais pas si cette stratégie est viable ou non - je devrais l'essayer. Il y a des détails importants que j'ai oubliés depuis longtemps. Des trucs comme: précision de la machine, erreur de la machine et erreur d'arrondi, etc.

Notez également que si vous n’utilisez pas e ^ x, mais que vous effectuez une croissance / décroissance avec une autre base telle que 2 ^ x ou 10 ^ x, la fonction polynomiale approximative change.

Answer 3

L'approche habituelle, pour élever a à b, pour un exposant entier, ressemble à ceci:

result = 1
while b > 0
  if b is odd
    result *= a
    b -= 1
  b /= 2
  a = a * a

Il est généralement logarithmique dans la taille de l’exposant. L'algorithme est basé sur l'invariant "a ^ b * result = a0 ^ b0", où a0 et b0 sont les valeurs initiales de a et b.

Pour les exposants négatifs ou non-entiers, des logarithmes, des approximations et une analyse numérique sont nécessaires. Le temps d'exécution dépendra de l'algorithme utilisé et de la précision pour laquelle la bibliothèque est optimisée.

Éditer: Comme il semble y avoir un intérêt, voici une version sans multiplication supplémentaire.

result = 1
while b > 0
  while b is even
    a = a * a
    b = b / 2
  result = result * a
  b = b - 1

Answer 4

Si j’écrivais une fonction Pow ciblant Intel, je renverrais exp2 (log2 (x) * y). Le microcode d'Intel pour log2 est sûrement plus rapide que tout ce que je pourrais coder, même si je pouvais me souvenir de mon calcul de première année et de l'analyse numérique de mes études supérieures.

Answer 5

Vous pouvez utiliser exp (n * ln (x)) pour calculer x ⁿ . X et n peuvent être des nombres en virgule flottante double précision. Le logarithme naturel et la fonction exponentielle peuvent être calculés à l'aide de la série de Taylor. Ici vous pouvez trouver des formules: http://fr.wikipedia.org/wiki/Taylor_series