[LeetCode] Sqrt_综合

[Problem]

Implement int sqrt(int x).

Compute and return the square root of x.

[Analysis]
牛顿方法，对于sqrt(S)，随便猜一个x (1 <= x <= S)，则sqrt(S) = x + e，其中e为误差。
第一次迭代：
    sqrt(S) = x_1 + e
    S = (x_1 + e)^2
    S = x_1^2 + 2ex_1 + e^2
    e = (S - x_1^2) / (2x_1 + e)
    相比于x，假设e非常小，则
    e ≈ (S - x_1^2) / 2x_1
第二次迭代：
    x_2 ≈ x_1 + e
        = x_1 + (S - x_1^2) / 2x_1
        = (x_1 + S/x_1)/2
第n+1次迭代：
    x_(n+1) ≈ x_n + e
          = x_n + (S - x_n^2) / 2x_n
          = (x_n + S/x_n)/2

更多方法可以参考：
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Approximations_that_depend_on_IEEE_representation
http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

[Solution]

class Solution {
      
public:
    int sqrt(int x) {
      
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(x == 0){
      
            return 0;
        }
       
        // iterative
        double pre = 1.0;
        double res = (double)x;
        while(res - pre){
      
            pre = res;
            res = 0.5*(res + x/res);
        }
        return res;
    }
};