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.

Solution 1

simple:

def poly(lst, x): 
  n, tmp = 0, 0
  for a in lst:
    tmp = tmp + (a * (x**n))
    n += 1

  return tmp

print poly([1,2,3], 2)

simple recursion:

def poly(lst, x, i = 0):
  try:
    tmp = lst.pop(0)
  except IndexError:
    return 0
  return tmp * (x ** (i)) + poly(lst, x, i+1)

print poly([1,2,3], 2)

Solution 2

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

Solution 3

def evalPoly(lst, x):
    total = 0
    for power, coeff in enumerate(lst): # starts at 0 by default
        total += (x**power) * coeff
    return total

Alternatively, you can use a list and then use sum:

def evalPoly(lst, x):
        total = []
        for power, coeff in enumerate(lst):
            total.append((x**power) * coeff)
        return sum(total)

Without enumerate:

def evalPoly(lst, x):
    total, power = 0, 0
    for coeff in lst:
        total += (x**power) * coeff
        power += 1
    return total

Alternative to non-enumerate method:

def evalPoly(lst, x):
    total = 0
    for power in range(len(lst)):
        total += (x**power) * lst[power] # lst[power] is the coefficient
    return total

Also @DSM stated, you can put this together in a single line:

def evalPoly(lst, x):
    return sum((x**power) * coeff for power, coeff in enumerate(lst))

Or, using lambda:

evalPoly = lambda lst, x: sum((x**power) * coeff for power, coeff in enumerate(lst))

Recursive solution:

def evalPoly(lst, x, power = 0):
    if power == len(lst): return (x**power) * lst[power]
    return ((x**power) * lst[power]) + evalPoly(lst, x, power + 1)

enumerate(iterable, start) is a generator expression (so it uses yield instead of return that yields a number and then an element of the iterable. The number is equivalent to the index of the element + start.

From the Python docs, it is also the same as:

def enumerate(sequence, start=0):
    n = start
    for elem in sequence:
        yield n, elem
        n += 1

Solution 4

Either with recursion, or without, the essence of the solution is to create a loop on "n", because the polynomial starts at x^0 and goes up to a_n.x^n and that's the variable you should also consider as an input. Besides that, use a trick called multiply and accumulate to be able to calculate partial results on each loop iteration.

View more solutions