1

[我对问题进行了全局编辑，使其更加“有用”和清晰]

我想知道expcmath 中函数实现的复杂性。

如果可能的话，我的复杂性是指算法复杂性。与浮点运算相比的其他成本（例如加法）

以下几行：

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

也许在这种情况下实际上不可能谈论算法复杂性，我们所能做的就是测试（参见下面的答案），但我不知道我们如何客观地量化浮点运算和调用 exp 之间的区别？

4

4 回答 4

4

一般来说，原始类型的复杂性应该非常快。正如评论者所提到的，有时会有关于它的说明，如果没有众所周知的快速算法，Knuth 对这些事情有很好的部分。

求幂的通常实现是平方乘法，它利用观察结果，即您可以将任何求幂分解为一定数量的平方加上最多一个乘法。的基本算法在这里n**k给出并且是O ( lg k)。

于 2010-10-20T16:27:47.660 回答
4

似乎复杂性实际上是恒定的，因为 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
于 2010-10-20T17:11:22.390 回答
2

在这里可以找到一种使用指令的快速exp实现。SSE

于 2010-10-20T16:53:55.803 回答
1

与其他浮点运算所花费的时间相比，您是否对求幂所花费的时间感兴趣？这将因实施而异，也因计算机而异（可能有不同的数学处理器），因此我们无法给出一个答案。

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

于 2010-10-20T17:11:00.097 回答