Evaluating Polynomial Coefficients

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

Solution 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+a0defpoly(lst, x):
    total = 0for a inreversed(lst):
        total = total*x+a
    return total

Solution 2:

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 3:

def evalPoly(lst, x):
    total =0for 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:

defevalPoly(lst, x):
        total = []
        for power, coeff inenumerate(lst):
            total.append((x**power) * coeff)
        returnsum(total)

Without enumerate:

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

Alternative to non-enumerate method:

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

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

defevalPoly(lst, x):
    returnsum((x**power) * coeff for power, coeff inenumerate(lst))

Or, using lambda:

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

Recursive solution:

defevalPoly(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:

defenumerate(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.

Solution 5:

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

lst = [7, 1, 2, 3]
x = 5print(evalPoly(lst, x, 3))

Equation to evaluate is - 3x^3 + 2x^2 + x + 7 when x = 5, result is - 437