Solution – Binary Search

If you don’t remember Newton’s method, then this problem can be solved using Binary Search.

Note that the goal is not to find the exact square root r but to find the floor(r). So we terminate the loop when narrowing down the range to 1.

Notice that we calculate x/mid rather than mid*mid to avoid data overflow.

public int sqrt(int x) { if (x < 2) return x; int low = 0, high = x; while (high - low > 1) { int mid = low + (high - low) / 2; int div = x / mid; if (mid == div) return mid; if (mid < div) low = mid; else high = mid; } return low; }

This algorithm runs in time O(logx).

Solution - Babylonian method

The key idea of Babylonian method is that if root is an underestimate of x, then x/root must be an overestimate and the average of the two may reasonably provide a better approximation.

Babylonian method is derived from Newton's method as shown below.

To find the square root of S, it is equivalent to find an x such that f(x) = x^2 - S = 0. And thus, Newton's method uses f(x) and its derivative to approach a better approximation iteratively.

The process is as follows:

Let r_0 be an initial guess.

r_(i+1) = ( r_i + x / r_i ) / 2 for abs(r_(i+1) - r_i) >= e), where e is desired approximation.

To reduce the converge iterations, we use a rough estimation of 2^(floor(d/2)) as the initial estimate, where d is the number of binary digits of x.

public int sqrt(int x) { // initial guess, x_0 = 2^(D/2) int root = 1; for (int digit = 0, origin = x; origin > 1; origin >>= 1, ++digit, root <<= (digit & 1)); // calculate root double r0 = 0, r1 = 1.0*root; while (Math.abs(r1 - r0) > 0.01) { r0 = r1; r1 = (r0 + x/r0) / 2; } return (int)r1; }

If the initial guess can be found in constant time, this algorithm runs in time O(loglogn).