Page 380 - Matrix Analysis & Applied Linear Algebra

376 Chapter 5 Norms, Inner Products, and Orthogonality

then
0
1
c = γ n−1 b n−1 + γ n−2 b n−2 + ··· + γ 1 b + γ 0 b = p(b),
0
1
d = δ n−1 b n−1 + δ n−2 b n−2 + ··· + δ 1 b + δ 0 b = q(b),
and it follows from (5.8.11) that the product cd is given by
1
0
cd = p(b)q(b)=[c d] 2n−2 b 2n−2 +[c d] 2n−3 b 2n−3 +···+[c d] 1 b +[c d] 0 b .
It looks as though the convolution c d provides the base-b representation for
cd, but this is not quite the case because it is possible to have some [c d] k ≥ b.
For example, if c = 201 10 and d = 425 10 , then
 
5
     2 
1 5  
2
c d =     =   ,
0
 14 
2 4  4 
8


0
so
2
4
1
0
3
cd =(8×10 )+(4×10 )+ (14×10 )+(2×10 )+(5×10 ). (5.8.20)
But when numbers like 14 (i.e., greater than or equal to the base) appear in c d,
0
1
it is relatively easy to decompose them by writing 14 = (1×10 )+(4×10 ), so

0
3
2
2
2
1
14×10 = (1×10 )+(4×10 ) ×10 =(1×10 )+(4×10 ).
Substituting this in (5.8.20) and combining coefficients of like powers produces
the base-10 representation of the product
0
2
3
1
4
cd =(8×10 )+(5×10 )+(4×10 )+(2×10 )+(5×10 )= 85425 10 .
Computing c d directly demands n 2 multiplications, but using the FFT in
conjunction with the convolution theorem requires only about 3n log n mul-
2
tiplications, which is considerably less than n 2 for large values of n. Thus it
is possible to multiply very long base-b integers much faster than by using di-
rect methods. Most digital computers have binary integer multiplication (usually
64-bit multiplication not requiring the FFT) built into their hardware, but for
ultra-high-precision multiplication or for more general base-b multiplication, the
FFT is a viable tool.
Exercises for section 5.8
5.8.1. Evaluate the following convolutions.
           
1 4 −1 1 1 α 0
1
2
5
(a)     . (b)  0   0  . (c)    α 1  .

3 6 1 −1 1 α 2