public
anonymous / isPerfectSquare.py
Created

Subroutine that tests whether an integer is a perfect square using bisection search

  • Download Gist
isPerfectSquare.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
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)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.