pythonmathperfect-square

Check if a number is a perfect square

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

Speed is of no concern, for now, just working.

See also: Integer square root in python.

Solution

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