Horner's Rule
Typically, a polynomial is expressed as:
$f(x)=\sum_{k=0}^{n} a_k x^k$
or
Where a_{k} are real numbers representing the polynomial coefficients and
x^{k} are the polynomial variables.
The above polynomial is said to be of the n^{th} degree, i.e. deg(f(x)) = n where n represents the highest variable exponent.
Horner's rule for polynomial division is an algorithm used to simplify the process of evaluating a polynomial f(x) at a certain value x = x_{0} by dividing the polynomial into monomials (polynomials of the 1^{st} degree). Each monomial involves a maximum of one multiplication and one addition processes. The result obtained from one monomial is added to the result obtained from the next monomial and so forth in an accumulative addition fashion. This division process is also known as synthetic division.
To explain the above, let is re-write the polynomial in its expanded form;
This can, also, be written as:
The algorithm proposed by this rule is based on evaluating the monomials formed above starting from the one in the inner-most parenthesis and move out to evaluate the monomials in the outer parenthesis.
The algorithm is executed following the below steps:
2. Let b_{k} = a_{k}
3. Let b_{k - 1} = a_{k - 1} + b_{k}x_{0}
4. Let k = k - 1
5. If k ≥ 0 then go to step 3
Else End
This algorithm can, also, be graphically visualized by considering the 5^{th} degree polynomial given by:
which can be evaluated at x = x_{0} by re-arranging it as:
Another way to represent the results using this algorithm is through the tableau given below:
K | 5 | 4 | 3 | 2 | 1 | 0 |
b_{5} = a_{5} | b_{4} = a_{4} + x_{0}b_{5} | b_{3} = a_{3} + x_{0}b_{4} | b_{2} = a_{2} + x_{0}b_{3} | b_{1} = a_{1} + x_{0}b_{2} | b_{0} = a_{0} + x_{0}b_{1} |
Example: Evaluate the polynomial f(x) = x^{4} + 3x^{3} + 5x^{2} + 7x + 9 at x = 2
Solution:
Since the polynomial is of the 4^{th} degree, then n = 4
K | 4 | 3 | 2 | 1 | 0 |
Step | b_{4} = 1 | b_{3} = 3 + 2 * 1 | b_{2} = 5 + 2 * 5 | b_{1} = 7 + 2 * 15 | b_{0} = 9 + 2 * 37 |
Result | 1 | 5 | 15 | 37 | 83 |
Therefore, f(2) = 83.
Why do we have to do this?
Normally, when evaluating a polynomial at a certain value, we are used to substitute this value into the polynomial and do the math. We may also use or develop a mathematical computation application to do that, which is a necessity when we are dealing with complex polynomials with high degrees.
The way the computer processes a problem depends, mainly, on how you, as a programmer, describe it to the computer. You may design your application to solve the polynomial by direct substitution or using synthetic division according to Horner’s rule. The only difference between the two approaches is the speed at which the computer will solve the problem in either case.
The advantage offered by Horner's rule is that it reduces the number of multiplication operations. Knowing that the computer processing time for a single multiplication process is 5 to 20 times the processing time of an addition process, you can tell that designing your application to evaluate the polynomial using Horner’s rule will have significant improvement on the execution time taken by the computer.