C/C++ 的平方根

Question

我正在尝试实现我自己的平方根函数，该函数仅给出平方根的整数部分，例如3 的平方根 = 1。

我看到了方法here并尝试实现了方法

 int mySqrt(int x)
 {
    int n = x;
    x = pow(2, ceil(log(n) / log(2)) / 2);
    int y=0;

    while (y < x)
    {
        y = (x + n / x) / 2;
        x = y;
    }

    return x;

}

上述方法对输入 8 失败。另外，我不明白为什么它应该起作用。

另外，我试过方法here

int mySqrt(int x)
{

    if (x == 0) return 0;
    int x0 = pow(2, (log(x) / log(2))/2) ;
    int y = x0;
    int diff = 10;

    while (diff>0)
    {
        x0 = (x0 + x / x0) / 2; diff = y - x0;
        y = x0;
        if (diff<0) diff = diff * (-1); 

    }

    return x0;

}

在第二种方式中，对于输入 3，循环继续......无限期地（x0 在 1 和 2 之间切换）。

我知道这两种方法本质上都是 Netwon 方法的版本，但我无法弄清楚为什么它们在某些情况下会失败以及我如何才能使它们适用于所有情况。我想我在实施中有正确的逻辑。我调试了我的代码，但仍然找不到让它工作的方法。

Answer 1

试试这个

int n,i;//n is the input number
 i=0;
 while(i<=n)
 {
    if((i*i)==n)
    {
        cout<<"The number has exact root : "<<i<<endl;
    }
    else if((i*i)>n)
    {
        cout<<"The integer part is "<<(i-1)<<endl;
    }
    i++;
 }

希望对您有所帮助。

Answer 2

这个适合我：

uintmax_t zsqrt(uintmax_t x)
{
    if(x==0) return 0;
    uintmax_t yn = x; // The 'next' estimate
    uintmax_t y = 0; // The result
    uintmax_t yp; // The previous estimate
    do{
        yp = y;
        y = yn;
        yn = (y + x/y) >> 1; // Newton step
    }while(yn ^ yp); // (yn != yp) shortcut for dumb compilers
    return y;
}

returns floor(sqrt(x))

用 2 个估计值测试，而不是用单个估计值测试 0。

当我写这篇文章时，我注意到结果估计有时会波动。这是因为，如果精确结果是分数，算法只能在两个最接近的值之间跳转。因此，当下一个估计与前一个估计相同时终止将防止无限循环。

Answer 3

你可以试试 C sqrt 实现:

// return the number that was multiplied by itself to reach N.
unsigned square_root_1(const unsigned num) {
    unsigned a, b, c, d;
    for (b = a = num, c = 1; a >>= 1; ++c);
    for (c = 1 << (c & -2); c; c >>= 2) {
        d = a + c;
        a >>= 1;
        if (b >= d)
            b -= d, a += c;
    }
    return a;
}

// return the number that was multiplied by itself to reach N.
unsigned square_root_2(unsigned n){
    unsigned a = n > 0, b;
    if (n > 3)
        for (a = n >> 1, b = (a + n / a) >> 1; b < a; a = b, b = (a + n / a) >> 1);
    return a ;
}

用法示例：

#include <assert.h>
int main(void){
    unsigned num, res ;
    num = 1847902954, res = square_root_1(num), assert(res == 42987);
    num = 2, res = square_root_2(num), assert(res == 1);
    num = 0, res = square_root_2(num), assert(res == 0);
}

Source

C/C++ 的平方根

Square Root in C/C++

c++

math

square-root