Credit: Luther Blissett
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.
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
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.
Recipe 17.17 for another mathematical evaluation recipe.