How to Find Integer Square Roots in Python: Which Method is Best?

Calculating Integer Square Roots in Python

In Python, finding an exact integer square root can be a challenge. However, there are several methods available for this task.

One straightforward approach is to use Newton's method, which iteratively refines its estimate of the square root:

<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 method accurately calculates the largest integer square root, which can then be verified by multiplying it by itself to check if it matches the input number.

An alternative method is to use integer division to iteratively check for perfect squares:

<code class="python">def isqrt2(n):
    i = 1
    while i * i <= n:
        i += 1
    return i - 1</code>

This method has a simpler structure but is generally slower than Newton's method for large integers.

Finally, for Python versions 3.8 and later, the math module provides a built-in isqrt function that calculates the exact integer square root efficiently.

<code class="python">from math import isqrt

x = isqrt(49)  # returns 7</code>

By choosing the appropriate method based on the desired efficiency and Python version, you can accurately find integer square roots in various scenarios.

The above is the detailed content of How to Find Integer Square Roots in Python: Which Method is Best?. For more information, please follow other related articles on the PHP Chinese website!