Information Technology Reference
In-Depth Information
Let
2
be the ring of integers modulo 2. As shown in Problem
6.20
, the integer multi-
plication function
f
(
n
)
2
n
contains the convolution function over
f
(
n/
log
n
)
2
n
mult
:
B
→B
:
conv
2
n/
log
n
2
2
n/
log
n
2
→
. Thus, by Lemmas
10.11.2
and
10.13.1
the following holds:
THEOREM
10.13.2
There is an integer
n
0
>
0
such that for
n>n
0
the time
T
and space
S
used by any general branching program for binary integer multiplication
f
(
n
)
2
n
2
n
must
mult
:
B
→B
satisfy
ST
=Ω(
n
2
/
log
2
n
)
(10.10)
This lower bound can be achieved to within a factor of
O
(log
3
n
)
for space
Ω(log
n
)
≤
S
≤
O
(
n
)
.
Proof
Since the integer multiplication function depends on 2
n
variables, it can be com-
puted via table lookup with space
O
(
n
)
and time
O
(
n
)
, thereby meeting the lower bound
to within a factor of
O
(log
2
n
)
.
At the limit of small space,
S
=Θ(log
n
)
, the integer multiplication algorithm of
Section
10.5.3
provides a branching program. Since at most
log
2
n
bits suffice for the
carry from one power of 2 to the next, a branching program based on this algorithm has
at most
O
(
2
log
2
n
)
vertices at each of
n
2
levels. Thus, this program uses time
O
(
n
2
)
and
space
O
(log
n
)
, achieving the lower bound to within a factor of
O
(log
n
)
.
We sketch a procedure to fill in the range of space between these extremes and ask the
reader to complete the details. (See Problem
10.39
.) Assume that
k
divides
n
and represent
each
n
-bit binary number as an
(
n/k
)
-component base-2
k
number. As in the standard bi-
nary integer multiplication algorithm (where
k
=
1), form
n/k
(
n/k
)
-component numbers
through multiplication and shifting of consecutive base-2
k
components, as suggested below:
v
3
u
0
v
2
u
0
v
1
u
0
v
0
u
0
v
3
u
1
v
2
u
1
v
1
u
1
v
0
u
1
0
v
3
u
2
v
2
u
2
v
1
u
2
v
0
u
2
0
0
v
3
u
3
v
2
u
3
v
1
u
3
v
0
u
3
0
0
0
Here
u
r
and
v
s
are base-2
k
numbers. Multiply two such numbers through table lookup in
time and space
O
(
k
)
. Extend the algorithm for the base-2 case by replacing each subpro-
gram that multiplies two binary numbers by the table lookup program to multiply base-2
k
numbers. This new program adds products to a running sum of length
O
(log
n
)
bits. Thus,
it uses space
O
(
k
+log
n
)
and time
O
(
n
2
/k
)
, giving a space-time product of
O
(
n
2
log
n
)
for
k
≥
log
n
.
10.13.3 Matrix-Vector Product
The matrix-vector product function
f
(
n
)
n
n
computes the
n
-tuple
y
from the
:
R
→R
A×
x
n
-tuple
x
for a fixed
n
×
n
matrix
A
over
R
according to the rule
y
=
A
x
where
y
j
=
n−
1
k
=
0
a
j
,
k
x
k
for 0
≤
j
≤
n
−
1.
Search WWH ::
Custom Search