|I l@ve RuBoard|
17.18 Evaluating a Polynomial
Credit: Luther Blissett
We often need to evaluate a polynomial f(x), defined by its coefficients (c+c x x+c 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 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+x x (c+x x (c+.... 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.
17.18.4 See Also
Recipe 17.17 for another mathematical evaluation recipe.
|I l@ve RuBoard|