How could I check if a number is a perfect square?

Question

I'm pretty stumped with this one guys. I'm trying to toy with Python (as you can see with my previous questions) so I'd really love some help here. :P

Speeds is of no concern for now, just working.

Thanks!

Edit: I ended up doing it this way:

def isSquare(number):
    temp = math.sqrt(int(number))    
    if "." in str(abs(int(temp))):
        return False
    else:
        return True

Any criticism or suggestions?

Answer 1

>>> def f(x):
...     x = x ** 0.5
...     return int(x) == x
...
>>> for i in range(10):
...     print i, f(i)
...
0 True
1 True
2 False
3 False
4 True
5 False
6 False
7 False
8 False
9 True

Answer 2

You could binary-search for the rounded square root. Square the result to see if it matches the original value.

You're probably better off with FogleBirds answer - though beware, as floating point arithmetic is approximate, which can throw this approach off. You could in principle get a false positive from a large integer which is one more than a perfect square, for instance, due to lost precision.

Answer 3

I'm not sure of the Python, but you could do something like:

function isSquare(x) = x == floor(sqrt(x) + 0.5)^2

That is, take a number, find the square root, round it to the nearest integer, square it, and test if it's the same as the original number. (floor and adding 0.5 is done to prevent cases like sqrt(4) returning 1.9999999... due to floating point math, as Mike Graham pointed out.)

In case you're interested, there was once a very good discussion on the Fastest way to determine if an integer’s square root is an integer.

Edited for clarification.

Answer 4

The problem with relying on any floating point computation (math.sqrt(x), or x**0.5) is that you can't really be sure it's exact (for sufficiently large integers x, it won't be, and might even overflow). Fortunately (if one's in no hurry;-) there are many pure integer approaches, such as the following...:

def is_square(apositiveint):
  x = apositiveint // 2
  seen = set([x])
  while x * x != apositiveint:
    x = (x + (apositiveint // x)) // 2
    if x in seen: return False
    seen.add(x)
  return True

for i in range(110, 130):
   print i, is_square(i)

Hint: it's based on the "Babylonian algorithm" for square root, see wikipedia. It does work for any positive number for which you have enough memory for the computation to proceed to completion;-).

Edit: let's see an example...

x = 12345678987654321234567 ** 2

for i in range(x, x+2):
   print i, is_square(i)

this prints, as desired (and in a reasonable amount of time, too;-):

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

Please, before you propose solutions based on floating point intermediate results, make sure they work correctly on this simple example -- it's not that hard (you just need a few extra checks in case the sqrt computed is a little off), just takes a bit of care.

And then try with x**7 and find clever way to work around the problem you'll get,

OverflowError: long int too large to convert to float

you'll have to get more and more clever as the numbers keep growing, of course.

If I was in a hurry, of course, I'd use gmpy -- but then, I'm clearly biased;-).

>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0

Yeah, I know, that's just so easy it feels like cheating (a bit the way I feel towards Python in general;-) -- no cleverness at all, just perfect directness and simplicity (and, in the case of gmpy, sheer speed;-)...

Answer 5

Use newton's method to quickly zero in the nearest integer square root, then square it and see if it's your number. See isqrt.

Answer 6

Since you can never depend on exact comparisons when dealing with floating point computations (such as these ways of calculating the square root), a less error-prone implementation would be

import math
def is_square(integer):
    root = math.sqrt(integer)
    if int(root + 0.5) ** 2 == integer: 
        return True
    else:
        return False

Imagine integer is 9. math.sqrt(9) could be 3.0, but it could also be something like 2.99999 or 3.00001, so squaring the result right off isn't reliable. Knowing that int takes the floor value, increasing the float value by 0.5 first means we'll get the value we're looking for if we're in a range where float still has a fine enough resolution to represent numbers near the one for which we are looking.

Answer 7

1. Decide how long the number will be.
2. take a delta 0.000000000000.......000001
3. see if the (sqrt(x))^2 - x is greater / equal /smaller than delta and decide based on the delta error.

Answer 8

This response doesn't pertain to your stated question, but to an implicit question I see in the code you posted, ie, "how to check if something is an integer?"

The first answer you'll generally get to that question is "Don't!" And it's true that in Python, typechecking is usually not the right thing to do.

For those rare exceptions, though, instead of looking for a decimal point in the string representation of the number, the thing to do is use the isinstance function:

>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False

Of course this applies to the variable rather than a value. If I wanted to determine whether the value was an integer, I'd do this:

>>> x=5.0
>>> round(x) == x
True

But as everyone else has covered in detail, there are floating-point issues to be considered in most non-toy examples of this kind of thing.