MENUHorner's Rule
Typically, a polynomial is expressed as:
$f(x)=\sum_{k=0}^{n} a_k x^k$
or
Where ak are real numbers representing the polynomial coefficients and
xk are the polynomial variables.
The above polynomial is said to be of the nth 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 = x0 by dividing the polynomial into monomials (polynomials of the 1st 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 bk = ak
3. Let bk - 1 = ak - 1 + bkx0
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 5th degree polynomial given by:
which can be evaluated at x = x0 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 |
| b5 = a5 | b4 = a4 + x0b5 | b3 = a3 + x0b4 | b2 = a2 + x0b3 | b1 = a1 + x0b2 | b0 = a0 + x0b1 |
Example: Evaluate the polynomial f(x) = x4 + 3x3 + 5x2 + 7x + 9 at x = 2
Solution:
Since the polynomial is of the 4th degree, then n = 4
| K | 4 | 3 | 2 | 1 | 0 |
| Step | b4 = 1 | b3 = 3 + 2 * 1 | b2 = 5 + 2 * 5 | b1 = 7 + 2 * 15 | b0 = 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.
