17.18 Evaluating a Polynomial

Credit: Luther Blissett

17.18.1 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.

17.18.2 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

17.18.3 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, a multiplication, and an exponentiation for each degree of the polynomial. Horner's formula takes just a multiplication and an addition for each degree. On my system, evaluating 10,000 integer (long) polynomials of order 40 takes 3.37 seconds the naive way and 1.07 seconds the Horner way. With float arithmetic, it takes 0.53 seconds the naive way and 0.30 seconds the Horner way. Waste not, want not, I say.

17.18.4 See Also

Recipe 17.17 for another mathematical evaluation recipe.