# Currying def curry2(f): """Returns a function g such that g(x)(y) == f(x, y). >>> from operator import add >>> add_three = curry2(add)(3) >>> add_three(4) 7 """ def g(x): def h(y): return f(x, y) return h return g def uncurry2(g): """Returns a function f such that f(x, y) == g(x)(y). >>> from operator import add >>> uncurry2(curry2(add))(3, 4) 7 """ def f(x, y): return g(x)(y) return f # Direct implementations of iterative improvement def square_root(a): """Return the square root of a. >>> square_root(9) 3.0 """ x = 1 while x * x != a: x = square_root_update(x, a) return x def square_root_update(x, a): return average(x, a/x) def average(x, y): return (x + y)/2 def cube_root(a): """Return the cube root of a. >>> cube_root(27) 3.0 """ x = 1 while pow(x, 3) != a: x = cube_root_update(x, a) return x def cube_root_update(x, a): return (2*x + a/(x * x))/3 # Iterative improvement def golden_update(x): """The golden update rule returns a number closer to phi than x.""" return 1/x + 1 def golden_test(x): """Return whether x is the golden ratio (phi).""" return x * x == x + 1 def iter_improve(update, done, guess=1, max_updates=1000): """Iteratively improve guess with update until done returns a true value. >>> iter_improve(golden_update, golden_test) 1.618033988749895 """ k = 0 while not done(guess) and k < max_updates: guess = update(guess) k = k + 1 return guess def square_root_improve(a): """Return the square root of a. >>> square_root_improve(9) 3.0 """ def update(guess): return square_root_update(guess, a) def done(guess): return guess * guess == a return iter_improve(update, done) def cube_root_improve(a): """Return the cube root of a. >>> cube_root_improve(27) 3.0 """ def update(guess): return cube_root_update(guess, a) def done(guess): return guess * guess * guess == a return iter_improve(update, done) # Newton's method def approx_derivative(f, x, delta=1e-5): """Return an approximation to the derivative of f at x.""" df = f(x + delta) - f(x) return df/delta def newton_update(f): """Return an update function for f using Newton's method.""" def update(x): return x - f(x) / approx_derivative(f, x) return update def find_root(f, guess=1): """Return a guess of a zero of the function f, near guess. >>> from math import sin >>> find_root(lambda y: sin(y), 3) 3.141592653589793 """ return iter_improve(newton_update(f), lambda x: f(x) == 0, guess) def square_root_newton(a): """Return the square root of a. >>> square_root_newton(9) 3.0 """ return find_root(lambda x: x * x - a) def cube_root_newton(a): """Return the cube root of a. >>> cube_root_newton(27) 3.0 """ return find_root(lambda x: pow(x, 3) - a)