Labels

Sunday, March 22, 2015

Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

Naive Way: Return the square root of an integer as an integer. I use binary search. First I need to find maximum possible square root, which is (int)Math.sqrt(Integer.MAX_VALUE). And when it happens sqrt(x) is this value, can't use i^2 <= x <(i+1)^2 to end the loop since (i+1)^2 will overflow. List this case separately.

 public class Solution {  
   static final int MAX_SQRT = (int)Math.sqrt(Integer.MAX_VALUE);  
   public int sqrt(int x) {  
     int high = MAX_SQRT, low = 0;  
     while(low <= high){  
       int middle = (high+low)/2;  
       if(middle*middle <= x && middle == MAX_SQRT) return middle;  
       if(middle*middle <= x && (middle+1)*(middle+1) > x) return middle;  
       if(middle*middle > x)  
         high = middle-1;  
       else  
         low = middle+1;  
     }  
     return low;  
   }  
 }  

Improved Way: There is a mathematical method Newton's Method. I can't understand what is stated in the link. There are too mathematical. I understand from other one's algorithm newtons-iterative-method-in-c . In the answer of that question. Newton's method was explained.


No comments:

Post a Comment