wim - 1 year ago 137

Python Question

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...

Answer Source

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.