from operator import add, mul
from math import sqrt, e

def square_root(a):
    """Return the square root of a.

    >>> square_root(9)
    3.0
    """

    x = 1
    while x*x != a:
        x = (x + a/x) / 2
    return x

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

def cube_root(a):
    x = 1
    while pow(x, 3) != a:
        x = (2 * x + a / (x * x)) / 3
    return x

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

def iter_improve(update, done, guess = 1, max_updates = 1000):
    k = 0
    while not done(guess) and k < max_updates:
        guess = update(guess)
        k = k + 1
    return guess

def square_root_improve(a):
    def update(guess):
        return (guess + a / guess) / 2
    def done(guess):
        return guess * guess == a
    return iter_improve(update, done)

def nth_root_func_and_deriv(n, a):
    def root_func(x):
        return pow(x, n) - a
    def deriv(x):
        return n * pow(x, n - 1)
    return root_func, deriv

def nth_root_improve(n, a):
    root_func, deriv = nth_root_func_and_deriv(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)


###################
def identity(k):
    return k

def cube(k):
    return pow(k, 3)

def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total = total + term(k)
        k = k + 1
    return total