在不使用sqrt函数的情况下查找平方根？

Question

我发现了不使用sqrt函数找出平方根的算法,然后尝试进入编程.我最终使用C++中的这个工作代码

    #include <iostream>
    using namespace std;

    double SqrtNumber(double num)
    {
             double lower_bound=0; 
             double upper_bound=num;
             double temp=0;                    /* ek edited this line */

             int nCount = 50;

        while(nCount != 0)
        {
               temp=(lower_bound+upper_bound)/2;
               if(temp*temp==num) 
               {
                       return temp;
               }
               else if(temp*temp > num)

               {
                       upper_bound = temp;
               }
               else
               {
                       lower_bound = temp;
               }
        nCount--;
     }
        return temp;
     }

     int main()
     {
     double num;
     cout<<"Enter the number\n";
     cin>>num;

     if(num < 0)
     {
     cout<<"Error: Negative number!";
     return 0;
     }

     cout<<"Square roots are: +"<<sqrtnum(num) and <<" and -"<<sqrtnum(num);
     return 0;
     } 

现在问题是初始化声明中的迭代次数nCount(这里是50).例如,为了找出36的平方根,它需要22次迭代,所以没有问题,而找到15625的平方根需要超过50次迭代,所以它会在50次迭代后返回temp的值.请为此提供解决方案.

Answer 1

有一个更好的算法,最多需要6次迭代才能收敛到双倍数的最大精度:

#include <math.h>

double sqrt(double x) {
    if (x <= 0)
        return 0;       // if negative number throw an exception?
    int exp = 0;
    x = frexp(x, &exp); // extract binary exponent from x
    if (exp & 1) {      // we want exponent to be even
        exp--;
        x *= 2;
    }
    double y = (1+x)/2; // first approximation
    double z = 0;
    while (y != z) {    // yes, we CAN compare doubles here!
        z = y;
        y = (y + x/y) / 2;
    }
    return ldexp(y, exp/2); // multiply answer by 2^(exp/2)
}

算法从1开始作为平方根值的第一近似值.然后,在每一步,它通过取当前值y和之间的平均值来改善下一近似x/y.如果y= sqrt(x),它将是相同的.如果y> sqrt(x),则x/y< sqrt(x)大约相同的数量.换句话说,它会很快收敛.

更新:为了加速非常大或非常小的数字的收敛,改变sqrt()函数以提取二进制指数并从[1, 4)范围内的数字计算平方根.现在需要frexp()从<math.h>得到二进制指数,但可以通过提取来自IEEE-754数位格式,而无需使用得到这个指数frexp().

Answer 2

为什么不尝试使用巴比伦方法来找到平方根。

这是我的代码：

double sqrt(double number)
{
    double error = 0.00001; //define the precision of your result
    double s = number;

    while ((s - number / s) > error) //loop until precision satisfied 
    {
        s = (s + number / s) / 2;
    }
    return s;
}

祝好运！