10K's

1. When solving the leetcode 176 Valid Perfect Square, someone introduced a way to find the root of a high class functions.

2. The main idea is by doing tension again and again, we coud get a solution that is close to the root in a accepatble difference.

3. So the linear function for the purple line is: $y = f(x_{0}) + f'(x_{0}) * (x - x_{0})$, if we want get the next x(n+1), y = 0.

4. So we could get x by move thing to the other side $x = {x_0 - f'(x_0) \over f'(x_0)}$.

5. In that question(leetcode 367), a square is corresbonded to function like: $f(x) = x^2 - n$, $f'(x) = 2x$.

6. So we get $x_{n+1} = {1 \over 2} * (x_{n} + {n \over x_{n+1}})$.

7. And the solution for this question is we continue looking for a value that just equals to the number(n), if exist return true otherwise return false. The code is like:

    public boolean isPerfectSquare(int num) {
        int x = num;
        while (x * x > num) {
            x = 1/2 * (x + num / x);
        }
        return x * x == num;
    }

8. There is another thing I want to explain is why we use num as n. From the graph of a square function like: $f(x) = x^2 - num$, we are trying to find a solution for it,

9. Useful links

   1. 如何通俗易懂地讲解牛顿迭代法求开方（数值分析）？ - 马同学的回答 - 知乎
   2. 简洁易懂的可视化牛顿迭代法推导