Python Cookbook

Evaluating a Polynomial

Credit: Luther Blissett

Problem

You need to evaluate a polynomial function, and you know that the obvious way to evaluate a polynomial wastes effort; therefore, Horner’s well-known formula should always be used instead.

Solution

We often need to evaluate a polynomial f(x), defined by its coefficients (c[0]+c[1] x x+c[2] x x2+...), at a given point x. There is an obvious (naive) approach to this, applying the polynomial’s definition directly:

def poly_naive(x, coeff):
    result = coeff[0]
    for i in range(1, len(coeff)):
        result = result + coeff[i] * x**i
    return result

However, this is a substantial waste of computational effort, since raising to a power is a time-consuming operation. Here, we’re wantonly raising x to successive powers. It’s better to use Horner’s well-known formula, based on the observation that the polynomial formula can also be indifferently written as c[0]+x x (c[1]+x x (c[2]+.... In other words, it can be written with nested parentheses, but without raise-to-power operations, only additions and multiplications. Coding a loop for it gives us:

def poly_horner(x, coeff):
    result = coeff[-1]
    for i in range(-2, -len(coeff)-1, -1):
        result = result*x + coeff[i]
    return result

Discussion

Python programmers generally emphasize simplicity, not speed. However, when equally simple solutions exist, and one is always faster (even by a little), it seems sensible to use the faster solution. Polynomial evaluation is a case in point. The naive approach takes an addition, ...