開根号的幾類算法總結

二分法開根号

首先是最基本的二分開根号，這個比較容易了解，複雜度比起下面講的牛頓疊代法要高，更容易了解。

下面給出代碼：

#define eps 0.00001
float SqrtByDichotomy(float n)
{
    if(n<)
    {
        return -;
    }
    else
    {   
        float low,up,mid,last; 
        low=,up=(n>=?n:); 
        mid=(low+up)/; 

        do
        {
            if(mid*mid>n)
                up=mid; 
            else 
                low=mid;

            last=mid;
            mid=(up+low)/;         

        }while(fabsf(mid-last) > eps);   //求浮點數x的絕對值

        return mid; 
    }
}
           

牛頓疊代法

這個算法的複雜度比二分法低。

牛頓疊代法——百度百科裡面講的很清楚。

http://baike.baidu.com/view/643093.htm

設r是 的根，選取 作為r的初始近似值，過點 做曲線 的切線L，L的方程為 ，求出L與x軸交點的橫坐标 ，稱x1為r的一次近似值。過點 做曲線 的切線，并求該切線與x軸交點的橫坐标 ，稱 為r的二次近似值。重複以上過程，得r的近似值序列，其中， 稱為r的 次近似值，上式稱為牛頓疊代公式。

如果隻是開根号運算的話，疊代公式為：

double SQR(double a){
    double x=a,y=;
    while(fabs(x-y)>){
        y=x;
        x=*(x+a/x);
    }
    return x;
}
           

還有其他算法先不看了，感覺把這兩種弄明白差不多了，有一種Carmack算法精度不夠，但是複雜度低，感興趣的時候可以看看。