69. Sqrt(x)

LeetCode

Newton Raphson method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        
        double a = x;
        double b = 0;

        while ((int)a != (int)b) {
            b = a;
            a = 0.5 * (b + x / b);
        }

        return (int)a;
    }
}

Remarks:

  1. TC: $O(\log \log x)$, SC: $O(1)$.

    Each iteration reduces the error quadratically, which means it has quadratic convergence and is very fast. (誤差が前回の誤差の二乗の速さで減少する)

  2. How to derive the formula?
    We are trying to calculate $\sqrt{S}$, so we are trying to find a $x$ such that $x^2 = S$.

    Which could be presented as $f(x) = x^2 - S$, to find the zero point.

    General Newtown Raphson:
    $$
    x_{n+1} = x_n - \frac{f(x_n)}{f’(x_n)}
    $$

    In this problem, $f(x) = x^2 - S$, $f’(x) = 2x$,

    So we have the iteration formula:

    $$
    x_{n+1} = x_n - \frac{x_n^2 - S}{2x_n} = \frac{1}{2}\left(x_n + \frac{S}{x_n}\right)
    $$

    Where $S$ is the parameter $x$ in the question.