Square Root – sqrt(x)

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

Leave a Reply

Your email address will not be published. Required fields are marked *