Qual è la complessità / costo reale di exp in cmath rispetto ad un flop?

Question

[ho curato a livello globale la questione di essere più "utile" e chiaro]

Mi chiedevo circa la complessità della implementazione della funzione exp in cmath.

Per la complessità, voglio dire complessità algoritmica, se possibile. Altrimenti costo rispetto ad un'operazione in virgola mobile (aggiunta per esempio)

Le seguenti linee:

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

di compilazione a:

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

exp deve essere caricata dinamicamente a runtime, ma non riesco a trovare molte informazioni in merito all'attuazione complessità algoritmica. Sembra che non c'è nessuna chiamata a un'istruzione speciale processore (almeno sulla mia piattaforma x86_64 con gcc) quindi ci deve essere un qualche implementazione che non riesco a trovare. Sulla mia mente, l'algoritmo è in grado di utilizzare la rappresentazione binaria dell'ingresso di avere una complessità molto debole, ma non sono stato in grado di trovare un valido riferimento su questo argomento.

Forse parlare di complessità algoritmica non è davvero possibile in questo caso, e tutto quello che possiamo fare è testare (cfr risposte sotto), ma non so come si possa quantificare oggettivamente la differenza tra un'operazione in virgola mobile e una chiamata a exp?

Answer 1

Sembra che la complessità è in realtà costante dal MSVC9 compilatore fa qualche bit-magia che coinvolge specifiche tabelle, maschere di bit e pregiudizi. Come ci sono pochi rami dopo tutto pipeline dovrebbe aiutare molto. Qui di seguito è quello che fa in realtà.

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

Parlando in generale, la complessità per i tipi primitivi dovrebbe essere molto veloce. Mentre i commentatori citano, a volte ci sono le istruzioni per essa, e se non ci sono ben noti algoritmi veloci, Knuth ha una sezione bene su queste cose.

Il solito attuazione a potenza è quadrato-and-moltiplicare che sfrutta l'osservazione che si può rompere qualsiasi elevamento a potenza fino in qualche numero di quadrature più al massimo un altro si moltiplicano. L'algoritmo di base per n**k è dato qui ed è O ( lg k).

Answer 3

Qui si può trovare un'implementazione veloce exp che utilizza le istruzioni SSE.

Answer 4

Sei interessato nel tempo impiegato da elevamento a potenza, rispetto al tempo impiegato da altre operazioni in virgola mobile? Che varieranno da esecuzione alla realizzazione, e anche da computer a computer (uno può avere un diverso processore matematico), quindi non c'è una risposta che possiamo dare.

L'approccio giusto, se volete sapere, è quello di scrivere funzioni e loro il tempo di prova. Loop attraverso milioni assegnazioni e tempo in virgola mobile che, cappio poi attraverso un milione assegnazioni virgola mobile di esponenziali e tempo che, quindi sottrarre. Attenzione per l'ottimizzatore su questo, come se non si utilizza il risultato delle assegnazioni è permesso di rimuovere l'intero ciclo. Saprete che i tempi di esecuzione estremamente veloci che non variano con la dimensione del ciclo.