Information Technology Reference
In-Depth Information
a
1
=?
0
1
b
1
=?
b
1
=?
0,1
0
1
a
2
=?
a
2
=?
0
1
0
1
b
2
=?
b
2
=?
b
2
=?
b
2
=?
1
1
0
0,1
0,1
0
a
3
=?
a
3
=?
0
1
0
1
b
3
=?
b
3
=?
b
3
=?
b
3
=?
1
1
0,1
0
0,1
0
c
=
0
c
=
1
c
=
a
1
b
1
+
a
2
b
2
+
a
3
b
3
(mod
2
)
Figure 10.20
A branching program to compute the inner product of two 3-vectors over the set
R
of integers modulo 2.
k
)
final states of a first table-lookup
rooting a table-lookup program at each of the
O
(
|R|
k
sums of the two column
k
-vectors.
program. Coalesce final states corresponding to the
|R|
2
k
)
vertices or space
O
(
k
log
This program has
O
(
)
and time
O
(
k
)
.
n/k
such stages
increase the number of vertices and time each by a factor of
n/k
. Since this process is
then repeated for each of the
n/k
rows of the block matrix, the space and time used are
O
(
k
log
|R|
|R|
+log(
n/k
))
and
O
(
n
2
/k
)
, respectively.
|R|
10.13.2 Integer Multiplication
To derive space-time lower bounds for integer multiplication, we could invoke the reductions
from this problem to cyclic shifting, as was done in Section
10.5.3
. However, as shown in
Section
10.10
, the space-time product for cyclic shifting is only
O
(
n
log
n
)
.Thus,weare
forced to use another reduction to obtain a strong space-time product lower bound, namely a
reduction from integer multiplication to convolution.
Search WWH ::
Custom Search