Integer square root in python

Newton's method works perfectly well on integers:

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

This returns the largest integer x for which x * x does not exceed n. If you want to check if the result is exactly the square root, simply perform the multiplication to check if n is a perfect square.

I discuss this algorithm, and three other algorithms for calculating square roots, at my blog.

Update: Python 3.8 has a math.isqrt function in the standard library!

I benchmarked every (correct) function here on both small (0…2²²) and large (2⁵⁰⁰⁰¹) inputs. The clear winners in both cases are gmpy2.isqrt suggested by mathmandan in first place, followed by Python 3.8’s math.isqrt in second, followed by the ActiveState recipe linked by NPE in third. The ActiveState recipe has a bunch of divisions that can be replaced by shifts, which makes it a bit faster (but still behind the native functions):

def isqrt(n):
    if n > 0:
        x = 1 << (n.bit_length() + 1 >> 1)
        while True:
            y = (x + n // x) >> 1
            if y >= x:
                return x
            x = y
    elif n == 0:
        return 0
    else:
        raise ValueError("square root not defined for negative numbers")

Benchmark results:

• gmpy2.isqrt() (mathmandan): 0.08 µs small, 0.07 ms large
• int(gmpy2.isqrt())*: 0.3 µs small, 0.07 ms large
• Python 3.8 math.isqrt: 0.13 µs small, 0.9 ms large
• ActiveState (optimized as above): 0.6 µs small, 17.0 ms large
• ActiveState (NPE): 1.0 µs small, 17.3 ms large
• castlebravo long-hand: 4 µs small, 80 ms large
• mathmandan improved: 2.7 µs small, 120 ms large
• martineau (with this correction): 2.3 µs small, 140 ms large
• nibot: 8 µs small, 1000 ms large
• mathmandan: 1.8 µs small, 2200 ms large
• castlebravo Newton’s method: 1.5 µs small, 19000 ms large
• user448810: 1.4 µs small, 20000 ms large

(* Since gmpy2.isqrt returns a gmpy2.mpz object, which behaves mostly but not exactly like an int, you may need to convert it back to an int for some uses.)