Why is checking error less than 1 sufficient for Newton's method square root estimation integer?

user_11606097 0
Viewed 63

Problem is from this link: https://leetcode.com/problems/sqrtx

My question is the line while (Math.abs(x0-x1) >= 1) condition. I don't understand why the moment that condition breaks, the answer would be the floor of x1. Is there no case where the break condition occurs at something like x1 equals 7 point something, but the true square root is 6 point something, giving the wrong answer of 7 when the actual answer is 6?

From my testing, this seems to be an invariant, but I don't understand why.

This is the Newton's Method solution:

class Solution {
  public int mySqrt(int x) {
    if (x < 2) return x;

    double x0 = x;
    double x1 = (x0 + x / x0) / 2.0;
    while (Math.abs(x0 - x1) >= 1) {
      x0 = x1;
      x1 = (x0 + x / x0) / 2.0;
    }

    return (int)x1;
  }
}
algorithm
1 Answers

This is indeed clever, and not at all obvious.

The update rule we have is x1 = (x0 + x/x0)/2 = f(x0).

First question. What is f'(x0)?

f'(x0) = d/dx0 (x0 + x/x0) / 2
       = (1 - x/x0^2) / 2

Let's note some facts.

  1. If sqrt(x) < x0, then the derivative is positive. So f(x0) is strictly increasing over sqrt(x) < x0. But f(sqrt(x)) = sqrt(x). Therefore if sqrt(x) < x0 then sqrt(x) < f(x0).
  2. The derivative is always < 1. So x0 - f(x0) is also strictly increasing. That's the size of the step.
  3. We are treating x as a constant here. But we should also note that (as long as x0^2 < x), the larger x is, the smaller the step size gets.

Enough Calculus, let's do something harder - algebra!

Let's try our best to have it give an answer of k when it should be giving an answer of k-1. That means we want x < k*k. The larger x is, the smaller the step, so we'll make x as big as we can - namely k*k-1

We want k <= f(x0). But we also want x0 - f(x0) < 1. Keeping in mind point 2, let's try x0 = k+1 and see where our next point lands.

But

f(k+1) = f(x0)
       = (x0 + x/x0) / 2
       = ((k+1) + (k^2 - 1)/(k+1)) / 2
       = ((k+1)^2 + (k^2 - 1)) / (2 * (k+1))
       = ((k^2 + 2k + 1) + (k^2 - 1)) / (2 * (k+1))
       = (2 k^2 + 2k) / (2 * (k+1))
       = (2 * (k+1) * k) / (2 * (k+1))
       = k

And whoops - x0 - f(x0) == 1 which fails our condition. Increasing x0 from there will result in a larger step size (which means we aren't finished yet), and decreasing it gives us the right answer.

So the condition is proven mathematically correct.

But...let's test it. Here is a test in Python.

def my_sqrt(x):
    x0 = x
    x1 = (x0 + x/x0)/2
    while (1 <= abs(x1 - x0)):
        x0 = x1
        x1 = (x0 + x/x0)/2
    return int(x1)

for i in range(2, 1000000):
    if i == my_sqrt(i * i - 1):
        print(i)

This finds that if k is in (314161, 599326, 599327, ...) then you get the wrong answer. Why? Because it is a delicate condition, and even one ulp of error can mess up the answer.

user_5854110
Related