1#isqrt.py 2 3import math 4 5def isqrt(n): 6 if n == 0: return 0 7 high = n 8 low = 0 9 calcMid = lambda: (high - low) / 2 + low + 1 10 mid = calcMid() 11 while high > low: 12 sq = mid**2 13 if sq > n: 14 high = mid - 1 15 else: 16 low = mid 17 mid = calcMid() 18 return low 19 20if __name__ == "__main__": 21 for i in range(10000000): 22 sq = isqrt(i) 23 if sq != int(math.sqrt(i)): 24 print "Failed on {}: {}".format(i, sq) 25 elif i % 100000==0: print i 26