Sqrt(x)

问题描述

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

---

思路

本题应该是采用一种快速的收敛方法来接近最终解。一般的做法是采用 二分法，但是我今天要说的是另一种，Newton\’s method。

我们设\(f(x)\)为：

$$
f(x) = x^{2} - k
$$

其中k就是要求的平方和（题目中的int x），x是我们要求的根。问题转化为求\(f(x) = 0\)的根。

Newton\’s method推导公式：

$$
x{n+1} = x{n} - \frac{f(x{n})}{f^{‘}(x{n})}
$$

当\(x^{2} - k\)的差值小于一个很小值\(\epsilon\), 我们就认为该x就是要求的值。

---

Code

//最后要转换为int型
int mySqrt(int x) {
    double g = x;
    //Newton method
    while (abs(g*g - x) > 0.000001){
        g = (g + x / g) / 2;
    }

    return (int)g;
}