   ## Horner's Rule for a Polynomial and Its Derivative

So far we have found an efficient procedure for evaluating a polynomial at any . Next we develop a procedure for getting its derivative at the same .

Notice that for any we can divide by to get quotient and remainder: (2)

where the quotient polynomial has degree : It is easy to show that So if we can find the coefficients of the quotient polynomial , we can use Horner's algorithm to get .

If we substitute the polynomials into Eq. ( ), and equate coefficients of on the lhs and rhs and solve for the coefficients and remainder we get a series of equations that can be organized as a recursion relation: These equations should look familiar, because they are nothing but Horner's algorithm, derived in a different way. But now we see that the intermediate variable in the pseudocode actually holds the coefficients of the quotient polynomial ! If we are careful, we can use them to build a dual procedure for evaluating both and without the need to store them all.

Here is the pseudocode for the dual-purpose algorithm:

   Step 1: Set p = a[n] and q = 0
Step 2: Do steps 3 and 4 for i from n-1 to 0, decreasing by 1
Step 3: set q = p + x0 * q
Step 4: set p = a[i] + x0 * p
Step 5: The value of P(x_0) is p and the value of P'(x_0) is q

It is left as an exercise to check this pseudocode by playing computer with a simple example and with the special case .

Finally, we leave as an exercise to complete the Newton-Raphson code for finding the real roots of a general polynomial.   