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