寻找平方根，而无需使用sqrt函数？ [英] Finding square root without using sqrt function?

问题描述

我是找到了算法找出平方根，而无需使用sqrt函数，然后试图把进入编程。我结束了这方面的工作code在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\n";
     cin>>num;

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

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

现在的问题是初始化在declaratione迭代NCOUNT数（这里是50）。例如，要找出36平方需要22次迭代，因此而发现的15625平方根没问题需要超过50次迭代，所以它会经过50次迭代返回温度值。请给一个解决方案。

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.

推荐答案

您的算法是pretty的坏。有更好的算法，需要至多6次迭代收敛到最高precision双号：

Your algorithm is pretty bad. There is 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开始作为第一个近似平方根值。 然后，在每一个步骤，它通过利用电流值是和 X / Y 之间平均提高了下一个近似。如果是 = 的sqrt（x），这将是相同的。如果是> 的sqrt（x），然后 X / Y ＆LT; 的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（）从＆LT;文件math.h＆GT; 来得到二进制指数，但它有可能得到该指数由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屋！