Analysis of Algorithms : An Active Learning Approach

4.1 CALCULATING POLYNOMIALS 111

Solving these equations we find that we will do approximately N / 2 multi-

plications and (3N
 1) / 2 additions. This doesn't, however, include the mul-

tiplications to get the sequence of values x^2 ,x^4 ,x^8 ,...,x^2 k
^1 , which takes an

additionalk
 1 multiplications. Thus, there are about N / 2 + lg N total mul-

tiplications.

Figure 4.2 gives a comparison of the standard algorithm, Horner’s method,

and preprocessed coefficients. In comparing the last two, we see that we have

saved N / 2 
 lg N multiplications but at a cost of (N
 1) / 2 additions. By

most standards, trading a multiplication for an addition will result in a time sav-

ings, so using preprocessed coefficients is more efficient.

4.1.3

1. Give the factorization of the equation x^7 + 2x^6 + 6x^5 + 3x^4 + 7x^3 + 5x + 4
   that results from
   a. Horner’s method
   b. Preprocessed coefficients


2. Give the factorization of the equation x^7 + 6x^6 + 4x^4
   2 x^3 + 3x^2
   7 x + 5
   that results from
   a. Horner’s method
   b. Preprocessed coefficients

■FIGURE 4.1

Work done for a

polynomial of

degree 7

Method Multiplications Additions

Standard 13 7

Horner’s 7 7

Preprocessed coefficients 5 10

■FIGURE 4.2

Work done for a

polynomial of

degreeN

Method Multiplications Additions

Standard

Horner’s

Preprocessed coefficients

2 N– 1 N

NN

N

---- 2 +lgN

3 N– 1

---------------- 2

■4.1.3 EXERCISES