Wednesday, November 5, 2014

Facebook: Calculate the square root of a double

Calculate the square root of a int
Warm-up Leetcode: Implement int sqrt(int x).

Idea: Binary search.

public class Solution {
    public int sqrt(int x) {
        if (x == 0) {
            return 0;
        }
        
        if (x < 0) {
            return -1;
        }
        
        long lo = 0;
        long hi = x / 2 + 1;
        
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long sq = mid * mid;
            if (sq == x) {
                return (int) mid;
            }
            
            if (sq < x) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        
        return (int) hi;
    }
}

Follow-up: Calculate the sqrt of a double
public class Solution {
    public double sqrt(double x) {
        if (x < 0) {
            return 0.0;
        }
        
        double eps = 1e-10;
        double lo = 0;
        double hi = Math.max(1.0, x);
        
        double mid = lo + (hi - lo) / 2;
        while (Math.abs(mid * mid - x) > eps) {
            if (mid * mid < x) {
                lo = mid;
            } else {
                hi = mid;
            }
            
            mid = lo + (hi - lo) / 2;
        }
        
        return mid;
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      double result = sol.sqrt(0.8);

      System.out.println("Result is " + result);
    }
}

Discussion:
Note that the initial high boundary is set to be
hi = Math.max(1.0, x);

That is simply because if a number is less than 1, its square root will be greater than the number itself. So if we set the high boundary to check as the number itself, you will never find that number. 

Newton Method:
为了方便理解,就先以本题为例:
   计算x2 = n的解,令f(x)=x2-n,相当于求解f(x)=0的解,如左图所示。
   首先取x0,如果x0不是解,做一个经过(x0,f(x0))这个点的切线,与x轴的交点为x1
   同样的道理,如果x1不是解,做一个经过(x1,f(x1))这个点的切线,与x轴的交点为x2
   以此类推。
   以这样的方式得到的xi会无限趋近于f(x)=0的解。
   判断xi是否是f(x)=0的解有两种方法:
   一是直接计算f(xi)的值判断是否为0,二是判断前后两个解xi和xi-1是否无限接近。

经过(xi, f(xi))这个点的切线方程为f(x) = f(xi) + f’(xi)(x - xi),其中f'(x)为f(x)的导数,本题中为2x。令切线方程等于0,即可求出xi+1=xi - f(xi) / f'(xi)。
继续化简,xi+1=xi - (xi- n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2。
有了迭代公式xi+1= (xi + n/xi) / 2,程序就好写了。
For Integer:
Code (Java):
public class Solution {
    public int sqrt(int x) {
        if (x < 0) {
            return -1;
        }
        
        if (x == 0) {
            return 0;
        }
        
        double pre = x / 2 + 1;
        double post = (pre + x / pre) / 2;
        
        double eps = 1e-10;
        
        while (Math.abs(pre - post) > eps) {
            pre = post;
            post = (pre + x / pre) / 2;
        }
        
        return (int) pre;
    }
}

For double everything is the same except for the input and return type.
Code (Java):
public class Solution {
    public double sqrt(double x) {
        if (x < 0) {
            return -1;
        }
        
        if (x == 0) {
            return 0;
        }
        
        double pre = x / 2 + 1;
        double post = (pre + x / pre) / 2;
        
        double eps = 1e-10;
        
        while (Math.abs(pre - post) > eps) {
            pre = post;
            post = (pre + x / pre) / 2);
        }
        
        return pre;
    }
}

No comments:

Post a Comment