Analysis of Algorithms : An Active Learning Approach

110 NUMERIC ALGORITHMS

If we divide p(x) by x^4 + 5, we will get a quotient and remainder polynomials,

and those are the values of q(x) and r(x), respectively. So, we need to divide as

follows:

This gives the equation

But we can apply this process to each of the polynomials for q(x) and r(x):

The results of all of this would be

If we look at this polynomial, we will see that there is one multiplication to

calculatex^2 and another to calculate x^4 (done as x^2 *x^2 ). There are also three

additional multiplications done in the equation, for a total of five multiplica-

tions. There are 10 additions done in this equation as well. Comparing this to

the other methods, we get the table in Fig. 4.1. This doesn’t look like a great

saving, but this is just for a limited case. We can get a general equation for the

amount of work done by looking carefully at the process. We first notice that

we do only one multiplication and two additions in Equation 4.3. This gives

the following set of recurrence relations for the number of multiplications,

M(k), and the number of additions, A(k), where N = 2k
 1:

) x (^7)  4 x (^6)  0 x (^5)  8 x (^4)  6 x (^3)  09 x (^2)  2 x 03

x^7
4 x^6
0 x^5
8 x^4
5 x^3
20 x^2
0 x
40
x^3
11 x^2  2 x
37
x^3  04 x^2  0 x 08
x^4  5
px()= ()x^4 + (^5) ()x^3 +++ 4 x^20 x 8 +()x^3 – 11 x^2 + 2 x– 37
x 14
) x (^3)  4 x (^2)  0 x 18 )

x^3
4 x^2  0 x 14
x^2
1
x 12
x^3
11 x^2  2 x
37
x
11

x^3  11 x^2
2 x 11
x^2  1
x
26
px()=()x^4 + (^5) []()x^2 – 1 ()x+ 4 +()x+ 12 +[]()x^2 + 1 ()x– 11 +()x– 26
M() 1 = 0
Mk()= 2 Mk()– 1 +1 for k> 1
A() 1 = 0
Ak()= 2 Ak()– 1 +2 for k> 1