Skip to content

Instantly share code, notes, and snippets.

Created June 25, 2012 09:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anonymous/2987635 to your computer and use it in GitHub Desktop.
Save anonymous/2987635 to your computer and use it in GitHub Desktop.
Subroutine that tests whether an integer is a perfect square using bisection search
def isPerfectSquare(x):
""" integer x => True if x is perfect square, False otherwise. """
# A perfect square cannot be negative
if(x < 0):
return False
# Test for the base 16 properties of squares
# In base 16, a square number can end only with 0,1,4 or 9 and
# - in case 0, only 0,1,4,9 can precede it,
# - in case 4, only even numbers can precede it.
# You can of course improve this condition by taking advantage of
# boolean evaluation short-circuiting.
condition = ((x % 16 == 1 or x % 16 == 9) or
(x % 16 == 0 and ((x % 256)/16 == 0 or (x % 256)/16 == 1
or (x % 256)/16 == 4 or (x % 256)/16 == 9)) or (x % 16 == 4 and
((x % 256)/16)%2 == 0))
if not(condition):
return False
low = 0
high = x
ans = (low + high)/2
# Bisection search
while ans**2 != x and low <= high:
#print low, high, ans
if(ans**2 < x):
low = ans + 1
else:
high = ans - 1
ans = (low + high)/2
if(ans**2 == x):
return True
return False
while True:
x = int(raw_input(""))
print isPerfectSquare(x)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment