Newton's Method and Integer Square Roots

Newton's method finds a root of f(x) = 0 by repeatedly sliding down the tangent line: x_next = x - f(x) / f'(x). Applied to f(x) = x^2 - n it becomes the ancient rule x_next = (x + n / x) / 2, which computes square roots with the number of correct digits roughly doubling every step. Interviews use it as the follow-up to "implement sqrt(x)" and for integer roots without floating-point error.

Intuition

Near a root, a smooth function looks like its tangent line. Replace the curve by the tangent at the current guess x, solve the linear equation instead, and take that solution as the next guess. For f(x) = x^2 - n the tangent step is x - (x^2 - n) / (2x) = (x + n/x) / 2: the average of x and n / x. If x is too large then n / x is too small, and their average is a better estimate.

Two facts make this robust for square roots:

• Quadratic convergence: the error roughly squares each step, so double precision is reached in a handful of iterations once you are close.
• Monotone from above: by the AM-GM inequality, (x + n/x) / 2 >= sqrt(n) for any positive x, so after the first step every guess is at or above the root and the sequence decreases. The integer version therefore stops at the first step that fails to decrease, and that value is exactly floor(sqrt(n)).

When to use it in interviews / OAs

• "Implement sqrt(x) (integer part) without library functions"; the binary search answer is expected first, Newton is the faster follow-up.
• "Is n a perfect square?" for numbers too large for floating point.
• Integer cube roots or k-th roots, square roots to a given precision.
• Any time int(math.sqrt(n)) might be wrong because n exceeds 2^53.

Template: integer square root

def isqrt_newton(n: int) -> int:
    # floor(sqrt(n)) for n >= 0, exact for arbitrarily large integers
    if n < 2:
        return n
    x = 1 << ((n.bit_length() + 1) // 2)  # a power of two at or above sqrt(n)
    while True:
        y = (x + n // x) // 2
        if y >= x:  # stopped decreasing: x is floor(sqrt(n))
            return x
        x = y


def isqrt_binary(n: int) -> int:
    # the same answer by binary search: largest x with x * x <= n
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi + 1) // 2  # upper middle, so lo = mid always makes progress
        if mid <= n // mid:  # mid * mid <= n, written to avoid overflow in C++/Java
            lo = mid
        else:
            hi = mid - 1
    return lo


def is_perfect_square(n: int) -> bool:
    r = isqrt_newton(n)
    return r * r == n

Binary search needs about log2(n) iterations (64 for 64-bit inputs); Newton needs only a few once the starting power of two is close. In Python, math.isqrt is the built-in exact version.

Template: real square root and k-th roots

def sqrt_newton(a: float, eps: float = 1e-15) -> float:
    # Newton's method on f(x) = x^2 - a, stopping on a relative tolerance
    if a == 0:
        return 0.0
    x = max(a, 1.0)  # start at or above the root
    while True:
        nx = (x + a / x) / 2
        if abs(x - nx) <= eps * nx:
            return nx
        x = nx


def iroot(n: int, k: int) -> int:
    # largest r with r**k <= n (n >= 0, k >= 2): Newton on x^k - n, starting above the root
    if n < 2:
        return n
    x = 1 << ((n.bit_length() + k - 1) // k)  # a power of two at or above the k-th root
    while True:
        y = ((k - 1) * x + n // x ** (k - 1)) // k
        if y >= x:
            return x
        x = y

For x^k - n the tangent step is x - (x^k - n) / (k x^(k-1)) = ((k - 1) x + n / x^(k-1)) / k, a weighted average with the same "approach from above" behavior.

Complexity

Binary search: O(log n) iterations. Newton from a power-of-two start: O(log log n) iterations in the quadratic phase, so a few iterations for 64-bit numbers. For huge integers each iteration costs one big division, which dominates. The floating-point version converges in about 5-10 iterations for typical inputs.

Common pitfalls

• Starting below the root in the integer version: the iteration can bounce between two values and the "stop when it no longer decreases" test fails. Always start at or above sqrt(n).
• Division by zero: never start at 0, and handle n = 0 and n = 1 up front.
• Overflow in C++/Java: mid * mid overflows for 64-bit inputs; compare mid <= n / mid instead.
• Trusting floating point: int(math.sqrt(n)) can be off by one for n > 2^53; correct it, or use the integer method.
• Absolute tolerances for real roots: a fixed 1e-9 is too loose for small inputs and may never be met for huge ones; use a relative tolerance.

Interview variations

• Sqrt(x) returning the integer part, and valid perfect square without built-ins.
• Sum of two squares: for each a, check whether n - a*a is a perfect square, or use two pointers up to isqrt(n).
• Integer cube root or k-th root of a big number.
• Square root to k decimal places: run the integer method on n * 10^(2k).
• Numerical root finding for monotone functions in general: Newton when the derivative is available, otherwise binary search or bisection.