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