Quelle est la complexité / coût réel de l'exp en cmath par rapport à un FLOP?

Question

[I globalement la question edited d'être plus "utile" et clair]

Je me demandais sur la complexité de la mise en œuvre de la fonction exp dans cmath.

Par la complexité, je veux dire la complexité algorithmique si possible. Sinon, le coût par rapport à une opération à virgule flottante (ajout par exemple)

Les lignes suivantes:

double x = 3;
double y = std::exp(x);

à la compilation:

...
19,23d16
       movq    %rax, -40(%rbp)
       movsd   -40(%rbp), %xmm0
       call    exp
       movsd   %xmm0, -40(%rbp)
       movq    -40(%rbp), %rax
...

exp doit être chargée au moment de l'exécution, mais je ne peux pas trouver beaucoup d'informations sur la mise en œuvre de la complexité algorithmique. Il semble qu'il n'y a pas appel à une instruction de processeur spécial (au moins sur ma plate-forme x86_64 avec gcc) il doit y avoir quelque part une mise en œuvre que je ne trouve pas. Sur mon esprit, l'algorithme est susceptible d'utiliser la représentation binaire de l'entrée d'avoir une complexité très faible, mais je n'ai pas été en mesure de trouver une référence précieuse sur ce sujet.

Pour parler peut-être de la complexité algorithmiques n'est pas vraiment possible dans ce cas et tout ce que nous pouvons faire est de tester (réponses voir ci-dessous) mais je ne sais pas comment nous pouvons quantifier objectivement la différence entre une opération à virgule flottante et un appel à exp?

Answer 1

Il semble que la complexité est en fait constante depuis le compilateur MSVC9 fait un peu de bit magique impliquant des tables spécifiques, bitmasks et préjugés. Comme il y a peu de branches après tout pipeline d'instructions devrait aider beaucoup. Voici ce qu'il fait.

unpcklpd    xmm0,xmm0 
movapd      xmm1,xmmword ptr [cv] 
movapd      xmm6,xmmword ptr [Shifter] 
movapd      xmm2,xmmword ptr [cv+10h] 
movapd      xmm3,xmmword ptr [cv+20h] 
pextrw      eax,xmm0,3 
and         eax,7FFFh 
mov         edx,408Fh 
sub         edx,eax 
sub         eax,3C90h 
or          edx,eax 
cmp         edx,80000000h 
jae         RETURN_ONE 
mulpd       xmm1,xmm0 
addpd       xmm1,xmm6 
movapd      xmm7,xmm1 
subpd       xmm1,xmm6 
mulpd       xmm2,xmm1 
movapd      xmm4,xmmword ptr [cv+30h] 
mulpd       xmm3,xmm1 
movapd      xmm5,xmmword ptr [cv+40h] 
subpd       xmm0,xmm2 
movd        eax,xmm7 
mov         ecx,eax 
and         ecx,3Fh 
shl         ecx,4 
sar         eax,6 
mov         edx,eax 
subpd       xmm0,xmm3 
movapd      xmm2,xmmword ptr Tbl_addr[ecx] 
mulpd       xmm4,xmm0 
movapd      xmm1,xmm0 
mulpd       xmm0,xmm0 
addpd       xmm5,xmm4 
mulsd       xmm0,xmm0 
addsd       xmm1,xmm2 
unpckhpd    xmm2,xmm2 
movdqa      xmm6,xmmword ptr [mmask] 
pand        xmm7,xmm6 
movdqa      xmm6,xmmword ptr [bias] 
paddq       xmm7,xmm6 
psllq       xmm7,2Eh 
mulpd       xmm0,xmm5 
addsd       xmm1,xmm0 
orpd        xmm2,xmm7 
unpckhpd    xmm0,xmm0 
addsd       xmm0,xmm1 
add         edx,37Eh 
cmp         edx,77Ch 
ja          ADJUST 
mulsd       xmm0,xmm2 
sub         esp,10h 
addsd       xmm0,xmm2 
movlpd      qword ptr [esp+4],xmm0 
fld         qword ptr [esp+4] 
add         esp,10h 
ret              

Answer 2

D'une manière générale, la complexité pour les types primitifs devrait être très rapide. Comme les commentateurs mentionnent, il y a parfois des instructions pour, et sinon il sont bien connus des algorithmes rapides, Knuth a une section bien sur de telles choses.

La mise en oeuvre habituelle pour exponentiation est carré et multiplication qui fait appel à l'observation que vous pouvez briser tout exponentiation vers le haut dans un certain nombre de quadrillages plus au plus un plus se multiplient. L'algorithme de base pour n**k est donnée et O ( lg k).

Answer 3

peut trouver une mise en œuvre rapide exp qui utilise les instructions de SSE.

Answer 4

Êtes-vous intéressé par le temps pris par exponentiation, par rapport à temps pris par d'autres opérations à virgule flottante? Cela varie d'une mise en application, ainsi que d'un ordinateur à (on peut avoir un processeur mathématique différent), donc il n'y a pas une seule réponse que nous pouvons donner.

La bonne approche, si vous voulez savoir, est d'écrire des fonctions de test et le temps eux. Boucle à travers un million affectations à virgule flottante et temps, puis à travers la boucle d'un million d'affectations à virgule flottante de temps exponentielles et que, ensuite soustraire. Méfiez-vous l'optimiseur sur celui-ci, comme si vous n'utilisez pas le résultat des travaux il est permis de retirer la totalité de la boucle. Vous saurez que par runtimes extrêmement rapides qui ne varient pas avec la taille de la boucle.