from operator import add, mul from math import sqrt, e def square(x): return x * x def make_adder(n): def adder(k): return add(n, k) return adder # Function composition def compose1(f, g): """Return a function h such h(x) == f(g(x)). >>> compose1(square, make_adder(2))(3) 25 """ def h(x): return f(g(x)) return h # Lambda expressions square = lambda x: x * x def summation(n, term): """Return the sum of the first n terms of a sequence. >>> summation(5, lambda x: pow(x, 3)) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total # 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 (x + a/x) / 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 pow(guess, 3) == a return iter_improve(update, done) # Newton's method for nth roots def nth_root_func_and_derivative(n, a): def root_func(x): return pow(x, n) - a def derivative(x): return n * pow(x, n-1) return root_func, derivative def nth_root_newton(a, n): """Return the nth root of a. >>> nth_root_newton(8, 3) 2.0 >>> nth_root_newton(10, 4) 1.7782794100389228 """ root_func, deriv = nth_root_func_and_derivative(n, a) def update(x): return x - root_func(x) / deriv(x) def done(x): return root_func(x) == 0 return iter_improve(update, done) # See online text for general Newton's method