newton.py (plain text)

"""Code for the Newton's method solver presented in lecture for CS61A. """

def iter_solve(update, done, guess=10, iteration_limit=32):
    """Return the result of repeatedly applying UPDATE, starting at GUESS,
    until DONE yields a true value when applied to the result. Causes a Python
    error if more than ITERATION_LIMIT applications of UPDATE are necessary.
    """
    while not done(guess):
        if iteration_limit <= 0:
            raise ValueError("failed to converge")
        guess, iteration_limit = update(guess), iteration_limit-1
    return guess

def newton_solve(func, deriv, start, tolerance):
    """Return x such that |FUNC(x)| < TOLERANCE, given initial estimate START
    and assuming DERIV is the derivative of FUNC.
    """
    def close_enough(x):
        return abs(func(x)) < tolerance
    def newton_update(x):
        return x - func(x) / deriv(x)

    return iter_solve(newton_update, close_enough, start)

def square_root(a):
    return newton_solve(lambda x: x*x - a, lambda x: 2 * x, 
                        a/2, 1e-5)

def logarithm(a, base=2):
    return newton_solve(lambda x: base**x - a, 
                        lambda x: x * base**(x-1),
                        1, 1e-5)

def find_root(func, start=1, tolerance=1e-9):
    def approx_deriv(f, delta = 1e-9):
        return lambda x: (func(x + delta) - func(x)) / delta
    return newton_solve(func, approx_deriv(func), start, tolerance)