Discrete Mathematics for Computer Science

574 CHAPTER 9 Recurrence Relations

The term 4T (n/2) accounts for the n/2-digit multiplications while m I -n accounts for

the additions and shifting operations (multiplications by a power of 2) required. Later, it

will be proved that the order of the complexity of this method is n^2 , which is the same order

of complexity as the usual method of multiplication. The usual method of multiplication is

shown for two 4-bit numbers in Figure 9.6.

1011

0111

1011

1011

1011

0000

1001 101

Figure 9.6 Usual method of multiplication.

Consider the following sequence of operations where X and Y are n-bit numbers (for

convenience, n = 2 k for some k) that are decomposed as before:

Calculation II

Decompose:

X=A.2f+B Y=C.21+D

Perform:

U <- (A + B) .(C + D)

V (-A.C

W÷-B.D

Z --V .2+ (U -V-W) .2+W

By expanding U - V - W, we see that Z is another way of calculating XY:

Z = V .2" + (U - V - W) .22 + W

= A .C .2n ± ((A + B) .(C ± D) - A .C - B. D) .2- + B .D

= A.C.2n +(A. D+ B.C).2f + B. D

= XY

For the moment, assume that no carry bits are generated by the additions used in

finding U. What we observe is that this method uses more additions and subtractions to

find XY than in Calculation I but has fewer multiplications. Since multiplications are the

more complex operation, this may be an acceptable trade-off. The recurrence relation that

describes this calculation of XY is

T(n) = 3T(n/2) + m2n