Instantly share code, notes, and snippets.

# anonymous/isPerfectSquare.py Created Jun 25, 2012

What would you like to do?
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)