查找平方根而不使用sqrt函数？

一尘不染

查找平方根而不使用sqrt函数？

algorithm

我正在寻找无需使用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的值。请为此提供解决方案。

阅读 282

2020-07-28

共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()。

2020-07-28