The integer square root function, or isqrt, is equivalent to floor(sqrt(x)) for non-negative x. For small x, the most convenient way to calculate isqrt is by calling int(x**0.5) or int(math.sqrt(x)), but if x is a large enough integer, the sqrt calculation overflows.
You can calculate the isqrt without any floating point maths, using just pure integer maths, allowing the function to operate with numbers far larger than possible with floats:
>>> n = 1234567*(10**1000)
>>> n2 = n*n
>>> math.sqrt(n2)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: long int too large to convert to float
>>> isqrt(n2) == n
True
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 | def isqrt(x):
if x < 0:
raise ValueError('square root not defined for negative numbers')
n = int(x)
if n == 0:
return 0
a, b = divmod(n.bit_length(), 2)
x = 2**(a+b)
while True:
y = (x + n//x)//2
if y >= x:
return x
x = y
|
The isqrt algorithm is a slight modification of the standard sqrt algorithm based on Newton's Method for solving x**2 - n = 0. Unfortunately, getting isqrt right is quite tricky, and most adaptations of the algorithm get it wrong. For example, take this supposed isqrt function:
def bad_isqrt(n):
x = n
y = (x + n//x) >> 1
while y-x > 1:
x = y
y = (x + n//x) >> 1
return y
based on a straight-forward, obvious but wrong modification of the algorithm suggested on Wikipedia: http://en.wikipedia.org/wiki/Integer_square_root
While bad_isqrt is usually correct, sometimes it is wrong, e.g. bad_isqrt(5) returns 3 instead of 2. Between 1 and 10000 inclusive, it only miscalculates the answer 22 times, which is easy to miss without adequate testing.
I am indebted to the answer from "fredrikj" here: http://stackoverflow.com/questions/1623375/writing-your-own-square-root-function
