Est-ce que 2 ** x est plus rapide à calculer que exp (x)?

12

Pardonnez la naïveté qui sera évidente dans la façon dont je pose cette question ainsi que dans le fait que je la pose.

Les mathématiciens utilisent généralement car c'est la base la plus simple / la plus agréable en théorie (en raison du calcul). Mais les ordinateurs semblent tout faire en binaire, est-il donc plus rapide sur une machine à calculer que ?exp2**xMath::exp(x)

isomorphismes
la source
7
De quel type de numéro parlez-vous? Entier de taille arbitraire? Virgule flottante de taille fixe? Virgule flottante à précision arbitraire?
Gilles 'SO- arrête d'être méchant'
@Gilles C'est un bon point. Je ne savais pas que la différence était importante.
isomorphismes
3
J'ai vu sur certaines calculatrices de poche Casio que la journalisation et la puissance d'un nombre non e sont beaucoup plus lentes que ln / exp
phuclv
2
Pour risquer d'être brutal, avez-vous essayé de chronométrer les deux et de voir lequel est le plus rapide? Ou parlez-vous de la vitesse dans un sens de complexité ? O(f(n))
jmite
1
La langue est en charge de sélectionner le moyen le plus rapide et fera un bon travail. Seulement dans le cas où la vitesse maximale est requise, et les mesures ont montré que cela est pertinent pour les performances si vous vous inquiétez de ce genre de choses
vonbrand

Réponses:

18

Comme il s'agit de CS et non de Stackoverflow, je vais supposer que vous posez une question sur l'analyse numérique, et (pour simplifier les choses) en virgule flottante IEEE-754 en particulier. Dans ce cas, la réponse à votre question dépend en partie de ce que vous entendez par «plus facile» et en partie des détails du système.

Aucun processeur moderne que je connaisse n'a une instruction intégrée qui fait exactement ce que vous attendez soit pour l' opération (que nous appellerons désormais , son nom habituel en C) ou 2 x ( ). Ils sont tous deux implémentés à l'aide de fonctions de bibliothèque.exexp2xexp2

Comme c'est le cas avec toutes les méthodes numériques pour les opérations transcendantales, il y a quelques cas particuliers à considérer:

exp(NaN) = NaN
exp(+Inf) = +Inf
exp(-Inf) = 0

Cependant, il y a une autre chose qui rend le problème un peu moins compliqué: le domaine utile est assez petit. Pour binary32, exp(x)débordements si environ et débordements si x > 88,7 environ. Exceptionnellement pour les opérations transcendantales, nous pouvons également ignorer le cas subnormal, car il est impossible de le distinguer de if est subnormal. Tout ce qui précède est également vrai pour , sauf que le domaine est légèrement différent.x<104x>88.7exp(x)1.0xexp2

Votre intuition a raison dans la mesure où la plupart des implémentations calculent . Cependant, le coût de cette multiplication par 1ex=2x/ln2 est trivial par rapport au reste de l'informatique. Une méthode typique utilise une table précalculée avecKéléments:1ln2exp2K

exp2(x)=2n×T[j]×P(y)

est la partie entière de x , le tableau T contient des valeurs de 2 j / K pour tout j dans la plage [ 0 , K ) , et P est une approximation polynomiale à 2 x (la quartique est suffisante pour binaire32) dans la plage [ 0 , 1nxT2j/Kj[0,K)P2x. Lapartie2nest bon marché, car elle ne fait que manipuler l'exposant. Test une table de recherche. AlorsPest susceptible d'être la partie coûteuse de l'opération.[0,1K)2nTP

Je dois souligner par souci d'exhaustivité que les FPU Intel x86 incluent une instruction appelée f2xm1, qui calcule pour x dans la plage [ - 1 , 1 ] . Cependant, sur un processeur moderne, il s'agit d'une instruction assez coûteuse et non canalisée, et vous êtes fortement découragé de l'utiliser. Comme l' indique à juste titre la section 3.8.5 du manuel de référence sur l'optimisation Intel :2x1x[1,1]

Bien que x87 prenne en charge les instructions transcendantales, la mise en œuvre de la bibliothèque logicielle de la fonction transcendantale peut être plus rapide dans de nombreux cas.

Edit: Il a été souligné dans les commentaires que je devrais expliquer une partie de la nouvelle terminologie utilisée dans IEEE 754-2008. Une partie du langage a changé depuis 1985 et 1987, et la plupart des gens connaissent beaucoup mieux l'ancien jargon.

Les termes "binary32" et "binary64" sont les nouveaux noms des nombres binaires à virgule flottante 32 bits et 64 bits, que l'ancien standard appelait respectivement "simple" et "double".

Le terme «nombre sous-normal» remplace le terme précédent «nombre dénormal» ou «nombre dénormalisé» .

Pseudonyme
la source
quand vous dites "subnormal" - vous ne voulez clairement pas dire "sub-gaussien"; voulez-vous dire "pire que [une référence de typicité]"?
isomorphismes
2
@isomorphismes Ici, «subnormal» concerne la façon dont les flottants sont implémentés. Voir les nombres dénormaux sur Wikipedia.
Paul Manta
Soit dit en passant, j'ai simplifié un peu trop la "méthode typique". Il est possible d'implémenter exp2 () et exp () avec une précision ulp en utilisant une seule petite extension (et assez facile à comprendre) à la méthode présentée ici, mais une explication de la petite extension facile à comprendre doublerait probablement la longueur de la réponse!
Pseudonyme du
6

2**x2x<<1 << x

gardenhead
la source
4
pas maintenant. x peut-être un type à virgule flottante
phuclv
1
x
Si xn'est pas un entier (par exemple 20.75), vous devez définir la mantisse sur 2et l'exposant sur la valeur arrondie de xcomme estimation la plus précise (une représentation précise n'étant pas possible). Ce qui est aussi beaucoup plus rapide que «pow».
Damon
1

Si 2**xest une fonction sur des entiers, alors je suis d'accord avec la réponse de Stephen, le décalage est moins cher. Mais je vois généralement cela comme 2^xet **pour indiquer l'exponentiation en virgule flottante. Dans ce cas, je m'attendrais à des performances similaires entre **et ^puisque et expet pow(l'opération sous-jacente pour **) sont tous deux des opérations d'approximation transcendantale.

Tim
la source
Intéressant, je ne savais pas que **c'était considéré comme un synonyme de la version à virgule flottante (et, stupide moi, j'avais oublié que les deux seraient différents).
isomorphismes
1

Puisque 2 ^ x = e ^ (x * ln 2) et e ^ x = 2 ^ (x * log2 (e)), vous ne vous attendriez pas à beaucoup de différence.

Pour x proche de zéro, on utiliserait généralement un polynôme e ^ x = 1 + x + x ^ 2/2 + x ^ 3/6 ..., bien optimisé pour couper le plus tôt possible tout en gardant l'erreur d'arrondi petite . Il est clair que 2 ^ x est un tout petit peu plus lent à calculer. "x proche de 0" correspond généralement aux valeurs de x où sqrt (1/2) <= e ^ x <= sqrt (2). La restriction de la plage de x garantit que le degré polynomial n'a pas besoin d'être choisi trop haut.

Pour un x plus grand, on calcule généralement 2 ^ x en laissant x = x '+ x' ', où x' est un entier et -0,5 <= x '' <= 0,5. 2 ^ x 'serait alors calculé en construisant un nombre à virgule flottante avec le motif binaire droit, et 2 ^ x' 'en utilisant la méthode e ^ x pour les petits x. Ici, 2 ^ x est un tout petit peu plus rapide. De plus, si x est grand (disons x = 100,3), la simple multiplication de x par log2 (e) introduirait une erreur d'arrondi inacceptable (car il y a beaucoup moins de bits fractionnaires), donc il faut faire plus attention.

Et j'espère qu'une bonne fonction de bibliothèque fera en sorte que chaque fois que x <= y, e ^ x <= e ^ y et 2 ^ x <= 2 ^ y, quelles que soient les erreurs d'arrondi. Réaliser ce genre de chose peut être délicat.

gnasher729
la source
0

Vous devez comprendre que les mathématiques sur un ordinateur sont effectuées de différentes manières par différents logiciels, en espérant trouver des réponses cohérentes. En regardant la plupart des logiciels, je pense que les ordinateurs se comportent bien - les ordinateurs et calculeront la réponse à long terme, même pour 0 ^ 0. Le problème est que des cas particuliers impliquent une "reconnaissance" qui ne se produit pas gratuitement dans les ordinateurs numériques. Cela signifie que c'est seulement dans les cas où la réponse accélérera "le plus" les choses que l'optimisation se produira. Mais dans ces cas, cela se produira extrêmement bien. Notez également que plusieurs reconnaissances différentes peuvent être nécessaires pour obtenir la bonne réponse. C'est ce qu'on appelle les niveaux d'optimisation de la vitesse et cela s'est produit dans la mesure professionnelle maximale dans la base de la plupart des logiciels appelés GNU "C". En effet, ici, des différences infimes dans le temps d'exécution d'un logiciel à l'autre et d'une machine à l'autre sont utilisées comme chiffres d'acceptation de la qualité. Dans d'autres interprètes, généralement uniquement si un "indicateur zéro" se produit, car un effet secondaire des calculs précédents accélérera la reconnaissance. comme 0 * x => C0.

marque
la source