Is there an integer square root somewhere in python, or in standard libraries? I want it to be exact (i.e. return an integer), and bark if there's no solution.
At the moment I rolled my own naive one:
def isqrt(n): i = int(math.sqrt(n) + 0.5) if i**2 == n: return i raise ValueError('input was not a perfect square')
But it's ugly and I don't really trust it for large integers. I could iterate through the squares and give up if I've exceeded the value, but I assume it would be kinda slow to do something like that. Also I guess I'd probably be reinventing the wheel, something like this must surely exist in python already...
isqrt() method in Python is used to get the integer square root of the given non-negative integer value n. This method returns the floor value of the exact square root of n or equivalently the greatest integer a such that a2 <= n. Note: This method is new in Python version 3.8.
sqrt() function returns the square root as a precise floating-point value. (This function is what you need 95% of the time.) The math. isqrt() function returns the square root as an integer value (meaning, rounded down to a whole number).
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With