快速实现pow(x, 0.5f)比快速计算sqrt(x)更快吗？

Question

我想知道快速实现pow()的方法，例如这个，是否比快速求解sqrt(x)更快地得到一个整数的平方根。我们知道

sqrt(x) = pow(x, 0.5f)

我无法测试速度，因为我没有找到快速实现sqrt的方法。 我的问题是：快速实现pow（x，0.5f）是否比快速实现sqrt（x）更快？

编辑：我的意思是powf-接受浮点数而非双精度数的pow。（双精度数更具误导性）

- Zaffy

---

该实现是一种近似方法，这意味着它的误差比使用sqrt要高得多，这也是为什么它可以更快的原因。 - Max

将参数和返回类型改为单精度会改变下面答案中的数字：pow逼近需要9个周期而不是6个周期（因为它是为双精度编写的，所以必须进行类型转换；可能可以重写为浮点数），powf需要16个周期而不是29个周期，sqrt逼近需要7个周期而不是10个周期（相反的效果，因为它是为浮点数编写的，所以类型转换消失了），sqrtf需要16个周期而不是29个周期。 - Eric Postpischil

数字0.5可以在IEEE浮点数中精确表示，因此编译器允许为您重写pow(x, 0.5)为sqrt(x)，并且当第二个参数为0.5时，C库允许从pow内部执行return sqrt(x)。我不知道是否有任何实现会执行这些操作，但如果有的话，我也不会感到惊讶。 - zwol

Answer 1

关于C标准库中的sqrt和pow，答案是否定的。

首先，如果pow(x, .5f)比sqrt(x)的实现更快，那么负责维护sqrt的工程师将使用pow(x, .5f)替换实现。

其次，商业库中sqrt的实现通常是专门针对该任务进行优化的，通常是由熟悉编写高性能软件并在汇编语言中编写以获得处理器提供的最佳性能的人员进行优化。

第三，许多处理器具有执行sqrt或协助计算sqrt的指令。（通常，有一个指令提供平方根倒数的估计值和一个指令用于改进该估计值。）

但是，你所链接的代码/问题尝试使用粗略估计的pow来粗略近似sqrt。

我将问题中提到的pow近似算法的最终版本转换为C语言，并在计算pow（3，.5）时测量其运行时间。 我还测量了系统（Mac OS X 10.8）pow和sqrt以及这里的sqrt近似值的运行时间（进行一次迭代并在末尾乘以参数以获得平方根，而不是其倒数）。

首先，计算结果：pow近似返回1.72101。 sqrt近似返回1.73054。 系统pow和sqrt返回的正确值为1.73205。

在MacPro4,1上以64位模式运行，pow近似需要约6个周期，系统pow需要29个周期，平方根近似需要10个周期，系统sqrt需要29个周期。 这些时间可能包括加载参数和存储结果的一些开销（我使用易失性变量强制编译器不要优化掉否则无用的循环迭代，以便我可以测量它们）。

（这些时间是“有效吞吐量”，实际上是从一个调用开始到另一个调用可以开始的CPU周期数。）

- Eric Postpischil

---

我写上面的内容是为了比较一个典型库中的sqrt和pow。然而，问题要求我们将sqrt与pow的近似值进行比较。在这种情况下，（非常糟糕的）pow近似可能会在一些平台上胜过sqrt。但请注意，pow近似声称典型误差为5％至12％。典型sqrt实现的误差通常约为0.000000000000222％。因此，这不是一个公平的比较。 - Eric Postpischil

确实。我在我的答案中考虑到了这一点，但我将对其进行编辑以使其更清晰明了。 - Max

如果愿意牺牲准确性，直接近似 sqrt() 会更快。 - Stephen Canon

用这么糟糕的误差来近似sqrt是微不足道的。只需操作浮点表示的位，将指数减半，然后在尾数上进行廉价修复即可... - R.. GitHub STOP HELPING ICE

Answer 2

在MSVC++ 2013 64位模式下，完全优化后运行以下代码的结果。sqrt()的性能提高了约9倍。

距离为2619435809228.278300

pow()的耗时为18413.000000毫秒

距离为2619435809228.278300

sqrt()的耗时为2002.000000毫秒

#define LOOP_KNT 249000000  // (SHRT_MAX * 1024)

int main(void)    {
    time_t start = clock();

    double distance = 0, result = 0;
    start = clock();
    for(int i=0; i<LOOP_KNT; i++) {
        result = pow(i, 0.50);
        distance += result;
    }
    printf("\nDistance is %f", distance);
   printf("\nPow() elapsed time was %f milliseconds", (double)clock() - (double)(start));

   distance = 0, result = 0;
   start = clock();
    for(int i=0; i<LOOP_KNT; i++) {
        result = sqrt(i);
        distance += result;
    }
    printf("\nDistance is %f", distance);
    printf("\nSqrt() elapsed time was %f milliseconds", (double)clock() - (double)(start));

   printf("\nHit any key to end program.\n");
   getchar();

   return 0;
}

不需要担心、理论化或者空谈。只需编写基准测试并观察结果。

- user2548100

---

谢谢回答；然而标准库中的 sqrt 和 pow 都非常慢。 - Zaffy

注意：我已在我的Cygwin 64位电脑上尝试了相同的操作-比率为1.04。 pow() vs sqrt()。 - chux - Reinstate Monica

@Zaffy，近乎正确只在马蹄铁和手榴弹中。25%的误差使您的链接方法毫无价值。而且它是用Java编写的，因此从一开始就性能不佳。“这真的非常紧凑。计算仅需要2次移位、1次乘法、2次加法和2次寄存器操作。就是这样！在我的测试中，通常误差范围在5%到12%之间，在极端情况下有时会高达25%。” - user1899861

Answer 3

一般来说，在相同的误差限制下，一个更具体的问题可以比一个更普遍的问题更加优化。

因此，您可以采用该算法，并将b替换为常数0.5，现在您拥有的sqrt()至少与pow()一样快。现在它是常数，编译器（或人类）可以基于此进行优化。

请注意，pow()函数是一种近似值，并且具有（相对较大的）误差，因此不像大多数库sqrt函数那样准确。如果您放宽对sqrt的实现的近似限制，确实可以使其至少与pow()一样快。

- Max

---

sqrt是一个代数函数，而pow()是一个超越函数，但在实践中它们都是近似值，通常采用牛顿-拉弗森迭代逼近法。http://www.sosmath.com/calculus/diff/der07/der07.html - user1899861

好的 sqrt() 实现可以被证明精度在 0.5 ULP 以内。pow() 很少有这种可证明的精度。好的实现通常会返回一个精度在 1 ULP 以内的结果。 - chux - Reinstate Monica