Sqrt(x)

Question

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to
return an integer, the decimal part will be truncated.

一开始想用二分法，可是觉得这样不好，数值计算问题应该有更通用的解法，现在就介绍一下牛顿法

牛顿法：(Newton’s method)又称为牛顿-拉弗森方法(Newton-Raphson method)，它是一种在实数域 和复数域上近似求解方程的方法

Solution

对于给定的\(x\)，\(y = \sqrt{x}\)
有\(x = y ^ 2\)，问题转化为
求方程\(f(x) = x ^ 2 - a = 0\)的近似根，其中\(x \ge 0\)

用牛顿法求解，关键在于找到递推式
切线方程：\(g(x) = f’(x_0)(x - x_0) + f(x_0)\)
当\(g(x) = 0\)时，\(x = x_0 - {f(x_0) \over f’(x_0)}\)
即\(x = x_0 - {x_0 ^ 2 - a \over 2 x_0}\)

递推式：\(x_n = \frac{1}{2} (x_{n-1} + {a \over x_{n-1}})\)

#include <cmath>

/**
 * Newton method
 * recursive equation:
 * x_n = 0.5 * (x_{n-1} + a / x_{n-1})
 */
class Solution {
public:
  int mySqrt(int x) {
    double r = 1;
    while (abs(r * r - x) >= 1) {
      r = (r + x / r) * 0.5;
    }
    return r;
  }
};

参考资料：
[1] wikipedia - Newton’s method