Page 550 - Discrete Mathematics and Its Applications

8.3 Divide-and-Conquer Algorithms and Recurrence Relations 529

Let
n
n
a = 2 A 1 + A 0 , b = 2 B 1 + B 0 ,
where

A 1 = (a 2n−1 ··· a n+1 a n ) 2 , A 0 = (a n−1 ··· a 1 a 0 ) 2 ,
B 1 = (b 2n−1 ··· b n+1 b n ) 2 , B 0 = (b n−1 ··· b 1 b 0 ) 2 .

The algorithm for fast multiplication of integers is based on the fact that ab can be
rewritten as
n
n
n
ab = (2 2n + 2 )A 1 B 1 + 2 (A 1 − A 0 )(B 0 − B 1 ) + (2 + 1)A 0 B 0 .
The important fact about this identity is that it shows that the multiplication of two 2n-bit
integers can be carried out using three multiplications of n-bit integers, together with additions,
subtractions, and shifts. This shows that if f (n) is the total number of bit operations needed to
multiply two n-bit integers, then

f(2n) = 3f (n) + Cn.

The reasoning behind this equation is as follows. The three multiplications of n-bit integers are
carried out using 3f (n)-bit operations. Each of the additions, subtractions, and shifts uses a
constant multiple of n-bit operations, and Cn represents the total number of bit operations used
by these operations. ▲

EXAMPLE 5 Fast Matrix Multiplication In Example 7 of Section 3.3 we showed that multiplying two
3
n × n matrices using the definition of matrix multiplication required n multiplications and
2
n (n − 1) additions. Consequently, computing the product of two n × n matrices in this way
3
requires O(n ) operations (multiplications and additions). Surprisingly, there are more efficient
divide-and-conquer algorithms for multiplying two n × n matrices. Such an algorithm, invented
by Volker Strassen in 1969, reduces the multiplication of two n × n matrices, when n is even, to
seven multiplications of two (n/2) × (n/2) matrices and 15 additions of (n/2) × (n/2) matrices.
(See [CoLeRiSt09] for the details of this algorithm.) Hence, if f (n) is the number of operations
(multiplications and additions) used, it follows that
2
f (n) = 7f (n/2) + 15n /4

when n is even. ▲
As Examples 1–5 show, recurrence relations of the form f (n) = af (n/b) + g(n) arise in
many different situations. It is possible to derive estimates of the size of functions that satisfy
such recurrence relations. Suppose that f satisfies this recurrence relation whenever n is divisible
k
by b. Let n = b , where k is a positive integer. Then

f (n) = af (n/b) + g(n)
2
2
= a f (n/b ) + ag(n/b) + g(n)
2
2
3
3
= a f (n/b ) + a g(n/b ) + ag(n/b) + g(n)
.
.
.
k−1
k k j j
= a f (n/b ) + a g(n/b ).
j = 0