与FLOP相比，cmath中exp的复杂性/实际成本是多少？

问题描述：

[我全局编辑的问题更“有用”，并明确]与FLOP相比，cmath中exp的复杂性/实际成本是多少？

我想知道在cmath中实现函数exp的复杂性。

通过复杂性，我的意思是算法的复杂性，如果可能的话。否则成本相比于浮点运算（加法例如）

下列行：

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

编译到：

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

exp必须被动态加载在运行时，但我不能找到许多关于实现算法复杂性的信息。看起来没有调用特殊的处理器指令（至少在我的x86_64平台上使用gcc），所以必须有一个我找不到的实现。在我看来，该算法很可能使用输入的二进制表示来具有非常弱的复杂性，但我一直无法找到有关此主题的有价值的参考。

也许在这种情况下讲算法复杂性是不可能的，我们所能做的只是测试（参见下面的答案），但我不知道如何客观量化浮点运算和呼叫exp？

这是针对平台和编译器的。你在使用哪一个？ – 2010-10-20 16:10:23

它应该是O（1）。 – ruslik 2010-10-20 16:10:55

您是在问一个具体的实现是多么复杂，或者一个特定实现的算法复杂性是多少？ – 2010-10-20 16:11:24

答

似乎复杂性实际上是恒定的，因为MSVC9编译器执行涉及特定表，位掩码和偏见的一些位魔法。由于很少有分支机构，毕竟指令管道应该有很大的帮助。以下是它的实际作用。

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

答

一般来说，原始类型的复杂度应该非常快。正如评论者所说，有时会有说明，如果没有知名的快速算法，Knuth在这方面有很好的部分。

指数运算的常用实现是square-and-multiply，它利用了可以将任何指数分成几个平方加上最多一个乘法的观察结果。 n**k的基本算法给出here，并且是O（lg k）。

我们怎样才能将exp调用与增加和乘法进行比较？ – Wok 2010-10-20 16:30:33

感谢您的回答。我认为必须有两种情况取决于平台：首先，exp有一个特定的硬件指令;其次，在C++运行时库的某个地方有一个方形和乘法算法。 – ThR37 2010-10-20 16:33:51

但是'exp（n）'是'O（log（n））'。我相信这仅仅是为了任意的精确度。 – Wok 2010-10-20 16:37:40

答

Here可以找到使用SSE指令的快速exp实现。

答

与其他浮点操作所花费的时间相比，您对指数运算所花费的时间感兴趣吗？这从实施到实施，以及从计算机到计算机（可能有不同的数学处理器）都有所不同，所以我们不能给出任何答案。

如果你想知道，正确的方法是编写测试函数并对它们进行计时。循环执行一百万个浮点赋值并对其进行计时，然后遍历一百万个浮点指数和时间，然后进行相减。注意这个优化器，就好像你不使用赋值的结果，它可以删除整个循环。通过极快的运行时间，您将会知道，不会因循环的大小而变化。

与FLOP相比，cmath中exp的复杂性/实际成本是多少？

相关推荐