开发者社区> 问答> 正文

怎样比较平方根倒数算法的效率?

问题源于这样一道作业题:

作业中提到的的那个invSqrt的代码如下:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration 
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

然后就自己写了个比较性能和精度的程序:

全选复制放进笔记
#include<stdio.h>
#include<math.h>
#include<time.h>
float Q_rsqrt(float number)        //从wiki上获取的源代码
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
    x2 = number * 0.5F;
    y = number;
    i = *(long *)&y;                       // evil floating point bit level hacking
    i = 0x5f3759df - (i >> 1);               // what the fuck?
    y = *(float *)&i;
    y = y * (threehalfs - (x2 * y * y));   // 1st iteration
    y = y * (threehalfs - (x2 * y * y));   // 2nd iteration, this can be removed
    return y;
}

int main()
{
    int LoopCount = 1000000;        //循环计算次数
    float dur = 0;        //时间间隔,初始化为0
    float x;        //待计算数
    printf("Please input a number:");        //输入提示
    scanf_s("%f", &x, sizeof(float));

    float y;
    clock_t t1 = clock();
    for (int i = 0; i < LoopCount; i++) {
        y =(float)( 1 / sqrt(x));
    }
    t1 = clock() - t1;
    printf("1/sqrt(%f)=%f\n", x, y);
    printf("%ld\n", t1);
    printf("Use Time_1:%.10f s\n", ((float)t1 / CLOCKS_PER_SEC));

    float z;
    clock_t t2 = clock();
    for (int j = 0; j < LoopCount; j++) {
        z = Q_rsqrt(x);
    }
    t2 = clock() - t2;
    printf("Q_rsqrt(%f)=%f\n", x, z);
    printf("%ld\n", t2);
    printf("Use Time_2:%.10f s\n", ((float)t2 / CLOCKS_PER_SEC));
    
    getchar();
    getchar();
    return 0;
}

之后,出现了一个很奇怪的问题:

screenshot
是的。。。C中的库函数效率基本上是下面那个算法的4倍!
但是,如果用C++中的库函数:

#include<stdio.h>
#include<cmath>
#include<time.h>
float Q_rsqrt(float number)        //从wiki上获取的源代码
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
    x2 = number * 0.5F;
    y = number;
    i = *(long *)&y;                       // evil floating point bit level hacking
    i = 0x5f3759df - (i >> 1);               // what the fuck?
    y = *(float *)&i;
    y = y * (threehalfs - (x2 * y * y));   // 1st iteration
    y = y * (threehalfs - (x2 * y * y));   // 2nd iteration, this can be removed
    return y;
}

int main()
{
    int LoopCount = 1000000;        //循环计算次数
    float dur = 0;        //时间间隔,初始化为0
    float x;        //待计算数
    printf("Please input a number:");        //输入提示
    scanf_s("%f", &x, sizeof(float));

    float y;
    clock_t t1 = clock();
    for (int i = 0; i < LoopCount; i++) {
        y =( 1 / sqrt(x));
    }
    t1 = clock() - t1;
    printf("1/sqrt(%f)=%f\n", x, y);
    printf("%ld\n", t1);
    printf("Use Time_1:%.10f s\n", ((float)t1 / CLOCKS_PER_SEC));

    float z;
    clock_t t2 = clock();
    for (int j = 0; j < LoopCount; j++) {
        z = Q_rsqrt(x);
    }
    t2 = clock() - t2;
    printf("Q_rsqrt(%f)=%f\n", x, z);
    printf("%ld\n", t2);
    printf("Use Time_2:%.10f s\n", ((float)t2 / CLOCKS_PER_SEC));
    
    getchar();
    getchar();
    return 0;
}

screenshot
因此。。。似乎C的效率比C++高了很多很多?现在在VS2015中的实现就连那个神奇的快速算法也比不过了?(还是。。。我这样的比较是不对的。。。)

疑惑中。。。

展开
收起
杨冬芳 2016-05-30 15:01:58 2630 0
1 条回答
写回答
取消 提交回答
  • IT从业

    凡是涉及到效率比较的问题,首先要确定的几个前提条件是:

    •是否使用了同样的编译器

    •是否使用了同样编译开关(比如优化开的是O几)

    •是否在同样的环境配置下运行的

    •运行的结果是否精确定量可重复

    在以上条件都确定以后,才能确认结果的可靠性,然后再考虑结果产生的原因。

    不知道题主的问题是否考虑了上述前提条件。

    题目中只测试了两个算法在同一个 case 下的结果,也许这个 case 对于一个算法是最优情况、对另一个算法是最差情况,所以结果不能说明问题。例如对于一个一般情况下是O(n log n)复杂度的算法,有可能最坏情况是O(n^2)、最优情况是O(n)。不能仅凭一个 case 就说明某个算法的优劣。

    2019-07-17 19:20:36
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载