不使用 sqrt 函数求平方根? [英] Finding square root without using sqrt function?

问题描述

我在不使用sqrt函数的情况下找出求平方根的算法，然后尝试投入编程.我最终在 C++ 中得到了这个工作代码

I was finding out the algorithm for finding out the square root without using sqrt function and then tried to put into programming. I end up with this working code in 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
";
     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 的值.请给出解决方案.

Now the problem is initializing the number of iterations nCount in the declaratione ( here it is 50). For example to find out square root of 36 it takes 22 iterations, so no problem whereas finding the square root of 15625 takes more than 50 iterations, So it would return the value of temp after 50 iterations. Please give a solution for this.

推荐答案

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

There is a better algorithm, which needs at most 6 iterations to converge to maximum precision for double numbers:

#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) 大约相同的数量.换句话说，它会很快收敛.

Algorithm starts with 1 as first approximation for square root value. Then, on each step, it improves next approximation by taking average between current value y and x/y. If y = sqrt(x), it will be the same. If y > sqrt(x), then x/y < sqrt(x) by about the same amount. In other words, it will converge very fast.

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

UPDATE: To speed up convergence on very large or very small numbers, changed sqrt() function to extract binary exponent and compute square root from number in [1, 4) range. It now needs frexp() from <math.h> to get binary exponent, but it is possible to get this exponent by extracting bits from IEEE-754 number format without using frexp().

这篇关于不使用 sqrt 函数求平方根?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！