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

This one works for me:

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))

Instead of testing for 0 with a single estimate, test with 2 estimates.

When I was writing this, I noticed the result estimate would sometimes oscillate. This is because, if the exact result is a fraction, the algorithm could only jump between the two nearest values. So, terminating when the next estimate is the same as the previous will prevent an infinite loop.