In an earlier post I mention that I didn’t know of a good method to determine whether a number was an integer squared or not. I spent some time looking into this and here’s what I came up with.

The naive solution

squares = Set(i*i for i in xrange(1,BIG)); def is_square(n): return n in squares

doesn’t really work for large values of BIG, since it has to compute all of those elements.

Googling around led me to the beast that is the integer square root. The wikipedia page led me to the following page, which had the following Python implementation:

def isqrt(n):
xn = 1
xn1 = (xn + n/xn)/2
while abs(xn1 - xn) > 1:
xn = xn1
xn1 = (xn + n/xn)/2
while xn1*xn1 > n:
xn1 -= 1
return xn1

Thus one can simply use:

def is_square(n): return isqrt(n)**2 == n

Sweet.

### Like this:

Like Loading...

*Related*

This entry was posted on February 13, 2008 at 3:05 am and is filed under Programming, Python.

November 15, 2009 at 11:09 am

Just shooting from the hip here…FWIW, now that Python 3 has bit_length, we can easily get a better first approximation:

xn = (x >> x.bit_length() // 2) + 1

November 15, 2009 at 11:38 am

Whoops, make that n, not x. I’ve tested it a little; for a really big number, it reduced the loop count from 289 to 7. Sweet.

June 17, 2011 at 5:37 am

Well, both Python 2 and 3 have log(), so:

xn = 1 << log(n + 1, 4)

Tom's method is slightly better than this, but they both take O(lg(lg(n)) steps through the loop instead of O(lg(n)). That's important if n has hundreds or millions of bits, especially since in those cases the individual steps can take quite a while.

The following takes about (lg(lg(n)) – 5) times through the loop, and those 5 fewer steps probably matter when 2**64 < n < 2**2**20, say.

if n <= 9e307:

xn = int(sqrt(n))

else:

p = log(n, 4)

xn = int(2.0 ** (p % 1 + 256)) << (int(p) – 256)

By the way the original routine needs a fix for when n == 0.

Thanks, y'all.