Sqrt(x)

I did not know the approach at first until I realized it's just basic math using Newton's method.

Update: 2015 - 01 - 07

Newton's method

x_(n + 1) = x_(n) + f(x_(n)) / f'(x_(n))

let f(a) = a^2 - x we want to find a so that f(a) ~ 0

a_(n+1) = a_(n) + f(a_(n)) / 2 * a_(n)

public class SquareRoot {
    public int sqrt(int x) {
        double prev = x / 2.0;
        double guess = prev / 2.0 + x / (2.0 * prev);
        while (Math.abs(guess - prev) > 0.1)
        {
            prev = guess;
            guess = prev / 2.0 + x / (2.0 * prev);
        }
        return (int)guess;
        
        
    }
}

The only problem I don't understand is that if alternatively I use

guess = prev  - x / (2.0 * pref);

I will exceed the time limit.

Another brilliant way is to use bisection method. The basic idea is, the square root of x must lie between 0 to x. So we keep reduce the range by comparing the square of mid with x, we will find our solution.

public class SqureRoot {
    public int sqrt(int x) {
        long low = 0;
        long high = x;
        while (low <= high)
        {
            long mid = (low + high) / 2;
            if (mid * mid == x)
                return (int)mid;
            else if (mid * mid < x)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return (int)high;
    }
}