import math


def py37_isqrt(n):
    """Return largest integer r such that r^2 <= n"""

    if n < 10000000000000000000000: # trial and error
        return math.floor(math.sqrt(n))
    else:
        # https://stackoverflow.com/a/53983683
        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")