Testing whether a number is a square integer

February 13, 2008

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.

Advertisements

3 Responses to “Testing whether a number is a square integer”

  1. Tom Zych Says:

    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

  2. Tom Zych Says:

    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.

  3. Steve Witham Says:

    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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: