Question

Suppose we want to evaluate the polynomial P(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ at point x.

1. Show that the following simple routine, known as Horner’s rule, does the job and leaves the answer in z.
   z = a_n
   for I = n-1 down to 0 :
   z = zx + a_i
2. How many additions and multiplications does this routine use, as a function of n ? Can you find a polynomial for which an alternative method is substantially better?

Short answer

1. The Horner’s rule, evaluates the polynomial and stores the answer in the z
2. One multiplication and one addition per loop. The Horner’s rule is the optimal method to find the polynomial.

Step-by-step solution

Explain polynomial

A polynomial expression is the algebraic form of expression that has the degrees for the variables. The polynomial expression has the same variable with multiple degrees.

Show that the following simple routine, known as Horner’s rule, does the job and leaves the answer in z.

(a)

Consider the Horner’s ruleas follows,

z = a_n

for i = n - 1 down to 0 :

z = zx + a_i

Let the loop invariant be 2 , when looping to i, then

$z_i=a_i+a_{i+1}x+a_{i+2}{x}^2+a_n{x}^{n-1}$, Then on the twenty first loop,

$\begin{array}{rcl}{z}_{i-1}& =& z_{i}x+a_{i-1}\\ & =& a_{i-1}+a_{i+1-1}x+a_{i+2-1}{x}^2+...a_n{x}^{n-(i-1)}\\ & =& a_{i-1}+a_{i}x+a_{i+1}{x}^2+...a_n{x}^{n-(i-1)}\end{array}$

Therefore, it has been proved that the Horner’s rule compute the polynomials and store at z

How many additions and multiplications does this routine use and which alternative method is substantially better

(b)

Consider the Horner’s ruleas follows,

z = a_n

for i = n -1 down to 0 :

z = zx + a_i

One multiplication and one addition per loop is performed, in total n multiplications and n additions are performed in the given scheme.

No alternative method calculates polynomial better than the Horner’s rule.

Therefore, One multiplication and one addition per loop. The Horner’s rule is the optimal method to find the polynomial.