9

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

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

我无法自己测试速度，因为我没有找到 sqrt 的快速实现。我的问题是：快速实现 pow(x, 0.5f) 是否比快速 sqrt(x) 快？

编辑：我的意思是 powf - pow 需要花车而不是双打。（双打更容易误导）

4

3 回答 3

23

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

首先，如果pow(x, .5f)比 的实现更快，则被sqrt(x)指派维护 sqrt 的工程师将用pow(x, .5f).

其次，商业库中的 sqrt 实现通常专门针对执行该任务进行优化，通常由熟悉编写高性​​能软件并使用或接近汇编语言编写以获得处理器可用性能的人员进行优化。

第三，许多处理器都有执行 sqrt 或帮助计算它的指令。（通常，有一条指令可提供平方根倒数的估计值，以及改进该估计值的指令。）

然而

您链接的代码/您提出的问题是关于尝试sqrt使用粗略近似的pow.

我将问题中提到的 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个周期。这些时间可能包括加载参数和存储结果的一些开销（我使用 volatile 变量来强制编译器不要优化掉否则无用的循环迭代，以便我可以测量它们）。

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

于 2012-08-04T17:52:25.637 回答
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;
}

无需绞尽脑汁、理论化或夸夸其谈。只需编写基准并观察结果。

于 2014-02-07T20:50:58.323 回答
1

一般来说，给定相同的误差约束，更具体的问题可以比更一般的问题更优化。

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

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

于 2012-08-04T17:51:47.217 回答