# Iterative Improvement

def square_root(a):
	""" return the square root of a

	>>>square_root(64)
	8.0
	"""
	x = 1
	while x * x != a:
		x = square_root_update(x, a)
	return x

def square_root_update(x, a):
	return (x + a / x) / 2

def cube_root(a):
	""" return the cube root of a

	>>>cube_root(27)
	3.0
	"""
	x = 1
	while x * x * x != a:
		x = cube_root_update(x, a)
	return x

def cube_root_update(x, a):
	return (2 * x + a / (x * x)) / 3


# Generalization of the iterative improvement approach

def improve(update, close, guess=1):
	""" Iteratively updates guess until the guess is close"""
	while not close(guess):
		guess = update(guess)
	return guess

def improve(update, close, guess=1, max_iteration=100):
	""" Iteratively updates guess until the guess is close or max_iteration is reached"""
	k = 0
	while not close(guess) and k < max_iteration:
		guess = update(guess)
		k += 1
	return guess

def approx_eq(p, q, tolerance=1e-15):
	return abs(p-q) < tolerance

def square_root_iter(a):
	"""return the square root of a"""
	def update(x):
		return square_root_update(x, a)
	def close(x):
		return approx_eq(x*x, a)
	return improve(update, close)

def cube_root_iter(a):
	"""return the cube root of a"""
	def update(x):
		return cube_root_update(x, a)
	def close(x):
		return approx_eq(x*x*x, a)
	return improve(update, close)


# Newton's method

def find_zero(f, df):
	""" find the zero of given function f"""
	def near_zero(x):
		return approx_eq(f(x), 0)

	def newton_update(f, df):
		def update(x):
			return x - f(x) / df(x)
		return update

	return improve(newton_update(f, df), near_zero)

def square_root_newton(a):
	"""return the square root of a"""
	def f(x):
		return x * x - a
	def df(x):
		return 2 * x
	return find_zero(f, df)

def cube_root_newton(a):
	"""return the cube root of a"""
	def f(x):
		return x * x * x - a
	def df(x):
		return 3 * x * x
	return find_zero(f, df)

def nth_root_newton(a, n):
	"""return the nth root of a"""
	def f(x):
		return pow(x, n) - a
	def df(x):
		return n * pow(x, n-1)
	return find_zero(f, df)