Horner's Method for Evaluating Polynomials

Added: 2026-05-18

[00:00:00]Here's a pretty neat method for evaluating a polynomial efficiently. If you had a degree D polynomial and you wanted to evaluate it at some value X, the standard thing to do with a pen and paper is to plug that value into the polynomial and compute each term one at a time. If this is done very naively by expanding each power and calculating each term independently, you can see that the number of multiplications is in the order of D squared. Maybe not ideal.

[00:00:23]Horner's method allows us to evaluate the degree D polynomial using just D multiplications and D additions. All it takes is to write the polynomial in a different way. Notice here we can factor an X out of the first four terms. Then of the first three terms inside the brackets, we can factor X out again. And one more time for these two terms. Now to evaluate this at X equals 5, we can start from the most deeply nested brackets and move outwards. And we completed the task using only four multiplications.

[00:00:50]A more general formula looks like this.

[00:00:53]To compute this algorithmically, you can start with the coefficient of the highest power term, multiply by X, and add the coefficient of the D minus one power term. And repeat. Multiply that result by X, and add the next coefficient, and so on, until you've processed all coefficients. Applying Horner's method in this way may also improve numerical stability when working with floating points. But one drawback is that each step relies on the previous result, which leaves fewer opportunities for parallel execution. So it's a good idea to benchmark this one in your environment first, especially since other methods and compiler optimizations exist.