Square Root in C/C++

Question

I am trying to implement my own square root function which gives square root's integral part only e.g. square root of 3 = 1.

I saw the method here and tried to implement the method

 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;

}

The above method fails for input 8. Also, I don't get why it should work.

Also, I tried the method 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;

}

In this second way, for input 3 the loop continues ... indefinitely (x0 toggles between 1 and 2).

I am aware that both are essentially versions of Netwon's method but I can't figure out why they fail in certain cases and how could I make them work for all cases. I guess i have the correct logic in implementation. I debugged my code but still I can't find a way to make it work.

Answer 1

Try this

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

Hope this helps.

Answer 2

You can try there C sqrt implementations :

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

Example of usage :

#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