# The following code should always work correctly,
# because integers don't overflow in Python.
# Accepts any type, returns type int or long.
# This routine is slow for large values,
# since the initial guess is 1.

def isqrt(i):
    "Compute the truncated square root of any non-negative integer."
    n = int(i)
    if n < 0:
	raise ValueError, "domain error"
	return
    xn = 1 # initial guess at the square root for the Babylonian iteration method
    xn1 = (xn + n/xn)/2
    while abs(xn1 - xn) > 1:
        xn = xn1
        xn1 = (xn + n/xn)/2
    while xn1*xn1 > n:
        xn1 -= 1
    if (xn1+1)*(xn1+1) <= n:
        raise ValueError, "failure of square root algorithm"
    return xn1