According the Lecture 6 of Berkeley Computer Science 61A – Fall 2012 ,i modify the newton method code for performance improve.

newtonMethodImprove.py

"""
INPUT: float, float, float
OUTPUT: bool
"""   
def approx_eq_1(x, y, tolerance=1e-18):
    return abs(x - y) <= tolerance

"""
INPUT: float, float, float
OUTPUT: bool
"""
def approx_eq_2(x, y, tolerance=1e-7):
    return abs(x - y) <= abs(x) * tolerance

"""
INPUT: float, float
OUTPUT: bool
"""
def approx_eq(x, y):
    if x == y:
        return True
    return approx_eq_1(x, y) or approx_eq_2(x, y)

"""
INPUT: function, function, int(float), int
OUTPUT: float
"""
def iter_improve(update, done, guess=1, max_updates=1000):
    k = 0
    last_guess = 0
    while not done(guess) and k < max_updates and not approx_eq(guess, last_guess):
        last_guess = guess
        guess = update(guess)
        k = k + 1
    print 'iterate times: %s' % k
    return guess

"""
INPUT: function, float, float
OUTPUT: float
"""   
def deriv(f, x, delta=1e-5):
    df = f(x + delta) - f(x)
    return df / delta

"""
INPUT: function
OUTPUT: function
"""   
def newton_update(f):
    def update(x):
        return x - f(x) / deriv(f, x)
    return update

"""
INPUT: function, int(float)
OUTPUT: float
"""   
def find_root(f, guess=1):
    done = lambda x: f(x) == 0
    return iter_improve(newton_update(f), done, guess)