compute the square root of x

sqr.py

# compute the square root of x

def sqr(x):
	prec = 1
	z = 2
	while z < x:
		prec = prec + 1
		z = z * 4
	# Here x <= (2**prec)**2
	a = 0
	while prec > -60:
		y = a + (2 ** prec)
		if x > y * y:
			a = y
		prec = prec - 1
	return a

#############
# test code
from math import sqrt

for a in [1, 1.9999, 2.0001, 1.5, 2.5, 10, 7, 24, 0.5, .3333333, 123132, 32849238749328]:
    b = sqr(a)
    print b - sqrt(a)
    print b, "** 2 =", b**2, "a =", a
    print '---'