How could I check if a number is a perfect square?
Speed is of no concern, for now, just working.
The problem with relying on any floating point computation (
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;-)...
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.
import math def is_square(i: int) -> bool: return i == math.isqrt(i) ** 2