23

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

4

10 回答 10

36

有一个更好的算法，它最多需要 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()from<math.h>来获取二进制指数，但可以通过从 IEEE-754 数字格式中提取位而不使用frexp().

于 2013-10-26T20:12:45.290 回答
11

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

这是我的代码：

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;
}

祝你好运！

于 2016-11-10T12:53:48.907 回答
2

完全删除你的nCount（因为有一些根，这个算法需要多次迭代）。

double SqrtNumber(double num)
{
    double lower_bound=0; 
    double upper_bound=num;
    double temp=0;

    while(fabs(num - (temp * temp)) > SOME_SMALL_VALUE)
    {
           temp = (lower_bound+upper_bound)/2;
           if (temp*temp >= num)
           {
                   upper_bound = temp;
           }
           else
           {
                   lower_bound = temp;
           }
    }
    return temp;
 }
于 2013-10-26T20:01:35.320 回答
2

当我发现这个问题很老并且有很多答案时，但我有一个简单且效果很好的答案..

#define EPSILON 0.0000001 // least minimum value for comparison
double SquareRoot(double _val) {
    double low = 0; 
    double high = _val;
    double mid = 0; 

    while (high - low > EPSILON) {
            mid = low + (high - low) / 2; // finding mid value
            if (mid*mid > _val) {
                high = mid;
            } else {
                low = mid;
            }    
    }   
    return mid;
}

我希望它对未来的用户有所帮助。

于 2016-03-03T06:37:09.430 回答
1

如果您需要在不使用的情况下求平方根sqrt()，请使用root=pow(x,0.5).

其中 x 是您需要找到其平方根的值。

于 2014-09-09T05:36:51.320 回答
0 
//long division method.
#include<iostream>
using namespace std;
int main() {
int n, i = 1, divisor, dividend, j = 1, digit;
cin >> n;
while (i * i < n) {
    i = i + 1;
}
i = i - 1;
cout << i << '.';

divisor  = 2 * i;
dividend = n - (i * i );
while( j <= 5) {
    dividend = dividend * 100;
    digit = 0;
    while ((divisor * 10 + digit) * digit < dividend) {
        digit = digit + 1;
    }
    digit = digit  - 1;
    cout << digit;
    dividend = dividend - ((divisor * 10 + digit) * digit);
    divisor = divisor * 10 + 2*digit;
    j = j + 1;
}
cout << endl;
return 0;
}
于 2015-06-23T19:27:28.393 回答
0

这是一个非常简单的递归方法。

double mySqrt(double v, double test) {
    if (abs(test * test - v) < 0.0001) {
        return test;
    }

    double highOrLow = v / test;
    return mySqrt(v, (test + highOrLow) / 2.0);
}
double mySqrt(double v) {
    return mySqrt(v, v/2.0);
}
于 2019-02-26T02:10:57.423 回答
0

这是一种非常简单但不安全的求数平方根的方法。不安全，因为它仅适用于自然数，您知道底数和指数是自然数。我必须将它用于既不允许使用#include<cmath> -library，也不允许我使用指针的任务。

效力 = 基数 ^ 指数

// FUNCTION: square-root
int sqrt(int x)
{
    int quotient = 0;
    int i = 0;

    bool resultfound = false;
    while (resultfound == false) {
        if (i*i == x) {
          quotient = i;
          resultfound = true;
        }
        i++;
    }
    return quotient;
}
于 2017-09-12T14:16:26.960 回答
-1

这是一个非常棒的代码，可以找到 sqrt，甚至比原始 sqrt 函数更快。

float InvSqrt (float x) 
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f375a86 - (i>>1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    x = x*(1.5f - xhalf*x*x);
    x = x*(1.5f - xhalf*x*x);
    x=1/x;
    return x;
}
于 2014-11-06T20:05:21.283 回答
-1

在查看了之前的回复后，我希望这将有助于解决任何歧义。如果以前的解决方案和我的解决方案的相似之处是虚幻的，或者这种求解根的方法不清楚，我还制作了一个图表，可以在这里找到。

这是一个能够解决任何 nth-root 的工作根函数

（为了这个问题，默认是平方根）

#include <cmath> 
// for "pow" function

double sqrt(double A, double root = 2) {
    const double e = 2.71828182846;
    return pow(e,(pow(10.0,9.0)/root)*(1.0-(pow(A,-pow(10.0,-9.0)))));
}

说明：

点击这里查看图表

这可以通过泰勒级数、对数属性和一些代数来实现。

举个例子：

log A = N
   x

*注：对于平方根，N = 2；对于任何其他根，您只需要更改一个变量 N。

1) 更改基数，将基数 ​​'x' 对数函数转换为自然对数，

log A   =>   ln(A)/ln(x) = N
   x

2) 重新排列以隔离 ln(x)，最终只是 'x'，

ln(A)/N = ln(x)

3) 将两边设为'e'的指数，

e^(ln(A)/N) = e^(ln(x))  >~{ e^ln(x) == x }~>  e^(ln(A)/N) = x

4）泰勒级数将“ln”表示为无限级数，

ln(x) = (k=1)Sigma: (1/k)(-1^(k+1))(k-1)^n

           <~~~ expanded ~~~>

[(x-1)] - [(1/2)(x-1)^2] + [(1/3)(x-1)^3] - [(1/4)(x-1)^4] + . . .

*注意：继续该系列以提高准确性。为简洁起见，在我的函数中使用了 10^9，它表示自然对数的级数收敛，大约 7 位，或百万分之一位，用于精度，

ln(x) = 10^9(1-x^(-10^(-9)))

5) 现在，只需将这个自然对数方程代入步骤 3 中获得的简化方程。

e^[((10^9)/N)(1-A^(-10^-9)] = nth-root of (A)

6）这个实现可能看起来有点矫枉过正；但是，它的目的是演示如何在无需猜测和检查的情况下求解根。此外，它还可以让您用自己的 pow 函数替换 cmath 库中的 pow 函数：

double power(double base, double exponent) {
    if (exponent == 0) return 1;
    int wholeInt = (int)exponent;
    double decimal = exponent - (double)wholeInt;
    if (decimal) {
        int powerInv = 1/decimal;
        if (!wholeInt) return root(base,powerInv);
        else return power(root(base,powerInv),wholeInt,true);
    }
    return power(base, exponent, true);
}

double power(double base, int exponent, bool flag) {
    if (exponent < 0) return 1/power(base,-exponent,true);
    if (exponent > 0) return base * power(base,exponent-1,true);
    else return 1;
}

int root(int A, int root) {
    return power(E,(1000000000000/root)*(1-(power(A,-0.000000000001))));
}
于 2015-12-18T03:26:36.823 回答