Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Integer square root in python

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

like image 883
wim Avatar asked Mar 13 '13 16:03

wim


People also ask

How do you square root integers in python?

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.

Does math sqrt return an integer?

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


1 Answers

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.

like image 189
user448810 Avatar answered Nov 04 '22 06:11

user448810