Check if a number is a perfect square

Solution 1:

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

Solution 2:

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

Python ≥ 3.8 has math.isqrt. If using an older version of Python, look for the "def isqrt(n)" implementation here.

import math

def is_square(i: int) -> bool:
    return i == math.isqrt(i) ** 2

Solution 3:

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)
    return integer == int(root + 0.5) ** 2

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.