# 6.00 Problem Set 4
#
# Successive Approximation
#

def evaluate_poly(poly, x):
    """
    Computes the polynomial function for a given value x. Returns that value.

    Example:
    >>> poly = (0, 0, 5, 9.3, 7)     # f(x) = 7x4 + 9.3x3 + 5x2
    >>> x = -13
    >>> print evaluate_poly(poly, x)  # f(-13) = 7(-13)4 + 9.3(-13)3 + 5(-13)2
    180339.9

    poly: tuple of numbers, length > 0
    x: number
    returns: float
    """
    result = 0.0
    for i in range(len(poly)):
        result += poly[i]*x**i
    return result


def compute_deriv(poly):
    """
    Computes and returns the derivative of a polynomial function. If the derivative is 0, returns (0,).

    Example:
    >>> poly = (-13.39, 0, 17.5, 3, 1)    # x4 + 3x3 + 17.5x2 - 13.39
    >>> print compute_deriv(poly)         # 4x3 + 9x2 + 35x
    (0, 35.0, 9, 4)

    Results such as (0.0, 35.0, 9.0, 4.0) are also acceptable.

    poly: tuple of numbers, length > 0
    returns: tuple of numbers
    """
    if len(poly) < 2:
        return (0,)
    deriv = ()
    for i in range(1, len(poly)):
        deriv += (poly[i]*float(i),)
    return deriv

def compute_root(poly, x_0, epsilon):
    """
    Uses Newton's method to find and return a root of a polynomial function.
    Returns a tuple containing the root and the number of iterations required to get to the root.

    Example:
    >>> poly = (-13.39, 0, 17.5, 3, 1)     #x4 + 3x3 + 17.5x2 - 13.39
    >>> x_0 = 0.1
    >>> epsilon = .0001
    >>> print compute_root(poly, x_0, epsilon)
    (0.80679075379635201, 8)

    poly: tuple of numbers, length > 1.
       Represents a polynomial function containing at least one real root.
       The derivative of this polynomial function at x_0 is not 0.
    x_0: float
    epsilon: float > 0
    returns: tuple (float, int)
    """
    x = x_0
    deriv = compute_deriv(poly)
    f_x = evaluate_poly(poly, x)
    ctr = 1
    while (abs(f_x) > epsilon):
        f_prime_x = evaluate_poly(deriv, x)
        x = x - (float(f_x)/f_prime_x)
        f_x = evaluate_poly(poly, x)
        ctr += 1
    return (x, ctr)

def compute_phi(phi_0):
    """
    Computes and returns an approximation of the golden ratio phi.

    Example:
    >>> print compute_phi(100.0)
    1.61803398898

    phi_0: float > 1.0
    epsilon: float > 0
    returns: float
    """
    phi_poly = (-1, -1, 1)
    return compute_root(phi_poly, phi_0, 0.000000001)[0]