python - Evaluating Polynomial coefficients

Question

I'm trying to write a function that takes as input a list of coefficients (a0, a1, a2, a3.....a n) of a polynomial p(x) and the value x. The function will return p(x), which is the value of the polynomial when evaluated at x.

A polynomial of degree n with coefficient a0, a1, a2, a3........an is the function

p(x)= a0+a1*x+a2*x^2+a3*x^3+.....+an*x^n

So I'm not sure how to attack the problem. I'm thinking that I will need a range but how can I make it so that it can handle any numerical input for x? I'm not expecting you guys to give the answer, I'm just in need of a little kick start. Do I need a for loop, while loop or could recursive be an option here?

def poly(lst, x)

I need to iterate over the items in the list, do I use the indices for that, but how can I make it iterate over an unknown number of items?

I'm thinking I can use recursion here:

    def poly(lst, x):
        n = len(lst)
        If n==4:
           return lst[o]+lst[1]*x+lst[2]*x**2+lst[3]*x**3
        elif n==3:
           return lst[o]+lst[1]*x+lst[2]*x**2
        elif n==2:
           return lst[o]+lst[1]*x
        elif n==1:
           return lst[o]
        else:
            return lst[o]+lst[1]*x+lst[2]*x**2+lst[3]*x**3+lst[n]*x**n

This works for n<=4 but I get a index error: list index out of range for n>4, can't see why though.

Answer 1

The most efficient way is to evaluate the polynomial backwards using Horner's Rule. Very easy to do in Python:

# Evaluate a polynomial in reverse order using Horner's Rule,
# for example: a3*x^3+a2*x^2+a1*x+a0 = ((a3*x+a2)x+a1)x+a0
def poly(lst, x):
    total = 0
    for a in reversed(lst):
        total = total*x+a
    return total