学步园

最近听说开平方算法挺难写，自己思考一下确实这些库函数只是一直在用，但是很少去思考如何实现的，sqrt在排序中使用频率非常的高，所以就研究了一下。大概有三种实现方式。

一、用二分的方法

        每次用中间数就试，如果大就到左区间选取中间数试，如果小就到右区间找中间数试，采用不断逼近的方式计算平方根，这种方式迭代次数有点多，且每次试验都要进行运算，效率不是很高，但是思路简单，巧妙的运用了二分的方法。

#define eps 0.00000001
float SqrtByBisection(float n)
{
    //小于0的按照你需要的处理
    if(n < 0)
        return n;
    float mid,last;
    float low,up;
    low=0,up=n;
    mid=(low+up)/2;
    do
    {
        if(mid*mid>n)
            up=mid;
        else
            low=mid;
        last=mid;
        mid=(up+low)/2;
    }
    //精度控制
    while(fabs(mid-last) > eps);
    return mid;
}

二、牛顿迭代法

这种方式的原理就是通过f(x) = x^2 - a = 0 的切线来逼近x^2 -a =0的的根，根号a就是f(x) =0的一个正实根，这个函数的导数是2x，也就是切线的斜率是2x，也就是x-f(x)/2x是比x更接近的近似值，带人方程得到f(x) = (x+a/x) / 2是更近似的值

float SqrtByNewton(float x)
{
 float val = x;//最终
 float last;//保存上一个计算的值
 do
 {
  last = val;
  val =(val + x/val) / 2;
 }while(fabs(val-last) > 0.0001);
 return val;
}

三、神一样的算法

float InvSqrt(float x)
{
 float xhalf = 0.5f*x;
 int i = *(int*)&x; // get bits for floating VALUE
 i = 0x5f3759df - (i>>1); // gives initial guess y0
 x = *(float*)&i; // convert bits BACK to float
 x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
 return x;
}

这个算法是卡马克(quake3作者)实现的，他真正牛B的地方是他选择了一个神秘的常数0x5f3759df 来计算那个猜测值，也是采用牛顿迭代法，但是选择的常数是绝妙的，能降上面的牛顿迭代法效率提高四倍，有空一定要拜读一下quake3的源代码，我在资源中放了一份欢迎下载