c ++ <cmath> SQRT()的实际计算复杂度

Question

CPU周期(或者,实质上,"速度")之间有什么不同

 x /= y;

和

 #include <cmath>
 x = sqrt(y);

编辑:我知道操作不等同,我只是随意提出x /= y作为基准x = sqrt(y)

Answer 1

您的问题的答案取决于您的目标平台.假设您正在使用最常见的x86 cpu,我可以给你这个链接http://instlatx64.atw.hu/ 这是一个测量指令延迟的集合(CPU在获得参数后获取结果需要多长时间)和它们如何为许多x86和x86_64处理器进行流水线操作.如果您的目标不是x86,您可以尝试自己测量成本或咨询CPU文档.

首先,您应该获得操作的反汇编程序(来自编译器,例如gcc:gcc file.c -O3 -S -o file.asm或通过编译二进制文件的解集,例如在调试器的帮助下).请记住,在您的操作中,需要加载和存储一个值,该值必须另外计算.

以下是friweb.hu的两个例子:

对于SQRT的Core 2 Duo E6700延迟(L)(x87,SSE和SSE2版本)

• 32位浮点数为29.58位为64位双倍; 69蜱为80位长双;

DIVIDE(浮点数):

• 18位为32位; 64位为32位; 38位为80位

对于较新的处理器,DIV和SQRT的成本较低且几乎相同,例如对于Sandy Bridge Intel CPU:

浮点SQRT是

• 14位为32位; 64位为21位; 24位为80位

浮点DIVIDE是

• 14位为32位; 64位为22位; 24位为80位

对于32位,SQRT甚至更快.

所以:对于较旧的CPU,sqrt本身比fdiv慢30-50%; 对于较新的CPU,成本是相同的.对于较新的CPU,两种操作的成本都会降低到旧CPU的成本; 对于更长的浮动格式,您需要更多时间; 例如,对于64位,您需要2倍的时间而不是32位; 但与64位相比,80位是便宜的.

此外,较新的CPU具有与标量(x87)相同速度的向量运算(SSE,SSE2,AVX).矢量具有2-4个相同类型的数据.如果您可以使用相同的操作将循环对齐到多个FP值,则可以从CPU获得更高的性能.

Answer 2

如果平方根函数没有在特殊硬件或软件中实现,大多数库函数将使用牛顿方法计算它,该方法以二次方式收敛.

牛顿方法是一种迭代方法:您进行初步猜测,计算试验结果,并将其用于下一次猜测.你会重复,直到你认为你的结果"足够接近".碰巧你可以用平方根来证明你需要多少次迭代.每次循环都会得到另外两位数的精度,因此大多数实现将在8-9个周期内收敛到双精度的精度限制.

如果你读了这仔细,你会看到牛顿迭代的方法是做两次减法,一次乘法,而每次迭代一个部门.