How to Find the Integer Square Root of a Number in Python?

Finding Integer Square Roots in Python

Python provides several ways to compute the square root of a number. However, none of these methods directly return an integer square root without approximations or exceptions.

One approach, as suggested in the initial code snippet, is to use the math.sqrt() function and round the result to the nearest integer. However, this approach may not be exact for large integers.

A more accurate method involves using Newton's method, which is an iterative technique for finding roots of equations. The following Python function implements Newton's method for integer square roots:

<code class="python">def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x</code>

This function initializes two variables, x and y, and iteratively updates them until convergence. x represents the best estimate of the integer square root, while y is an updated estimate that incorporates both the value of x and the integer division of n by x. The iteration stops when y becomes less than x, indicating that further refinement is unnecessary.

The returned value of isqrt() is the largest integer for which its square does not exceed n. To verify if the result is an exact integer square root, multiply the result with itself and compare it to n. Note that this function handles non-perfect squares by design, raising no exceptions.

While several other algorithms exist for calculating integer square roots, Newton's method is generally considered to offer a balance of accuracy, speed, and simplicity.

The above is the detailed content of How to Find the Integer Square Root of a Number in Python?. For more information, please follow other related articles on the PHP Chinese website!