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

解决方法：

1.牛顿法（Newton's method）

 化解：计算  x² = a 的解，令 y = x² - a，相当于求解 y = 0 的解，f(x) 如图。

   第一步：取 x₀ = a / 2 , 如果  x₀ 不是解，在点( x₀，y₀) 做切线 y - y₀ = (x - x₀) * y'₀ ，与 x 轴的交点为 x₁ = x₀ - y₀ / y'₀ = x₀ - (x_0² - a) / (2x₀) = (x₀ + a / x₀) / 2 。

  第二步：如果 x₁ 不是解，做一个经过  ( x₁，y₁) 这个点的切线，与x轴的交点为 x₂。

…………

结束条件：

a.  f( x_i ) ≈ 0;

b. x_{i ^≈} x_i-1^.

代码：

 

inline double ABS(double x){    return x > 0 ? x : (-1 * x);}class Solution {public:    int sqrt(int x) {        /* 用牛顿迭代法求浮点数的平方根 */          double g0 = 0, g1 = x;           while(ABS(g1-g0) > 0.9)           {               g0 = g1;               g1 = (g0 + (x / g0)) / 2;        }           return floor(g1); // (int)g1    }};

 

 2. 分治法（Divide and conquer）

a = 0 时，返回 0. 

a = 1 时，返回 1.

a > 1 时，返回的数在序列 1 与 a/2 之间，序列有序，所以可以用二分法查找。

代码如下：

class Solution {public:   int sqrt(int x){       /***********  二分法  ************/       /*********************************/       if(x == 0) return 0;       if(x == 1) return 1;       unsigned long long begin = 1, end = x >> 1;       while(begin < end)       {            unsigned long long mid = (begin + end) >> 1;            unsigned long long  tem = mid * mid;            if(tem == x) return mid;            else if(tem > x) end = mid -1;            else begin = mid + 1;       }       if(begin = end)       {          unsigned long long tem = end * end;          if(tem <= x) return end;          if(tem > x)  return end - 1;       }       else return end;    }};

 

3. 构造数字

从高位到低位，依次试探添加 1。

class Solution {public:    int sqrt(int x) {        int ans = 0;        int bit = 0X40000000;        while(bit > 0) {            ans |= bit;            if (ans > x / ans) {                ans ^= bit;            }            bit >>= 1;        }        return ans;    }};