sqrt函数的不同实现效果

首先，感谢参考的博文：http://www.cnblogs.com/pkuoliver/archive/2010/10/06/sotry-about-sqrt.html

由于最神奇的一种方法是我的一个偶像Carmack提出的，所以，就将这几种开方方法调试做了比较，

上代码

/*
* sqrt 的实现，即开根号
*/

#include <math.h>
#include <time.h>
#include <iostream>
#include <windows.h>

// 方案一 ： 二分法
float eps = 1e-7;
float sqrtByBinary(const float n)
{
if (n < 0)
return -1;
float smalls = 0, big = n;
float mid = (smalls + big) / 2;
float cur;
do {
if (mid*mid > n)
            big = mid;
else
            smalls = mid;
        cur = mid;
        mid = (smalls + big) / 2;
    } while (abs(mid - cur) > eps);
return  mid;
}

// 方案二 ； 函数库中的 sqrt 
float sqrtByMath(const float n)
{
if (n < 0)
return -1;
float t = sqrt(n);
return sqrt(n);
}


// 方案三 牛顿方法递减？
float sqrtByNewton(const float n)
{
if (n < 0)
return -1;
float last,val = n;
do {
        last = val;
        val = (val + n / val) / 2;
    } while (abs(last - val) > eps);
return last;
}


// 方案四 卡马克的神奇方法 ----------------------------
float sqrtByQ(float n)
{
long i;
float x2, y;
const float threehalfs = 1.5F;

    x2 = n*0.5F;
    y = n;
    i = *(long*)&y;
    i = 0x5f3759df - (i >> 1);
// 0x5f3759df //Carmack 的
// 0x5f37642f //Lomont 理论推导出的
// 0x5f375a86 //Lomont 暴力计算出的

    y = *(float*)&i;
    y = y*(threehalfs - (x2*y*y));  //1st iteration
    y = y*(threehalfs - (x2*y*y));  //2st iteration
return 1/y;
}

using namespace std;
void Test2()
{
unsigned int loopCount = 10000;

const int n = 65535;
    time_t t1, t2,t3;
    LARGE_INTEGER d1, d2, d3, d4,d5, d;
    QueryPerformanceFrequency(&d);

float sqrtN1 = sqrtByBinary(n);
    t1 = time(NULL);
    QueryPerformanceCounter(&d1);
for(int i = 0; i < loopCount;i++)
        sqrtN1 = sqrtByBinary(n);

float sqrtN2 = sqrtByMath(n);
    t2 = time(NULL);
    QueryPerformanceCounter(&d2);
for (int i = 0; i < loopCount; i++)
        sqrtN2 = sqrtByMath(n);
    t3 = time(NULL);
    QueryPerformanceCounter(&d3);

float sqrtN3 = sqrtByNewton(n);
for (int i = 0; i < loopCount; i++)
        sqrtN3 = sqrtByNewton(n);
    QueryPerformanceCounter(&d4);

float sqrtN4 = sqrtByQ(n);
for (int i = 0; i < loopCount; i++)
        sqrtN4 = sqrtByQ(n);
    QueryPerformanceCounter(&d5);

printf(" 统计sqrt(65536)计算多次的不同方法的时间效率，次数：%d\n", loopCount);
printf("-----------------------------------------------------------------\n");
printf("%10s%20s%20s\n", "方法", "时间", "计算结果");
printf("%10s%20.2f%20.8f\n", "二分法", (double)d2.QuadPart - (double)d1.QuadPart, sqrtN1);
printf("%10s%20.2f%20.8f\n", "系统函数", (double)d3.QuadPart - (double)d2.QuadPart ,sqrtN2);
printf("%10s%20.2f%20.8f\n", "Newton", (double)d4.QuadPart - (double)d3.QuadPart, sqrtN3);
printf("%10s%20.2f%20.8f\n", "Carmack", (double)d5.QuadPart - (double)d4.QuadPart, sqrtN4);
printf("%10s%20.2f%20.8f\n", "Newton(秒)", ((double)d4.QuadPart - (double)d3.QuadPart)/d.QuadPart, sqrtN3);      printf("-----------------------------------------------------------------\n");
}
void main()
{
    Test2();
    system("pause");
}