Information Technology Reference
In-Depth Information
An algorithm exists to compute
f
(
n
)
cyclic
that uses space
O
(
n
)
and time
O
(
n
log
n
)
, namely, that
satisfies the inequality
(
S
+
1
)
T
=
O
(
n
2
log
n
)
Proof
We leave the upper-bound proof to the reader. (See Problem
10.30
.)
We now apply this result to integer multiplication.
10.5.3 Integer Multiplication
To apply Grigoriev's method to the binary integer multiplication function
f
(
n
)
2
n
of Section
2.9
, we assemble a collection of results to show that with the proper encoding of one
of its two arguments,
f
(
n
)
mult
2
n
mult
:
B
→B
computes the logical shifting function
f
(
n
)
shift
(see Lemma
2.9.1
)
and when
n
is even the logical shifting function
f
(
n
)
shift
contains the cyclic shift function
f
(
n/
2
)
cyclic
as a subfunction (see Lemma
2.5.2
). Thus,
f
(
n
)
mult
contains
f
(
n/
2
)
cyclic
as a subfunction. We use
this fact to obtain a lower bound on the space-time product for integer multiplication.
THEOREM
10.5.3
Let
n
be even. Every pebbling strategy for straight-line programs computing the
binary integer multiplication function
f
(
n
)
2
n
2
n
requires space
S
and time
T
satisfying
mult
:
B
→B
the following inequality:
n
2
/
64
An algorithm exists for multiplying
n
-bit integers using space
O
(log
2
n
)
and time
O
(
n
2
)
,namely,
that satisfies
(
S
+
1
)
T
≥
(
S
+
1
)
T
=
O
(
n
2
log
2
n
)
Proof
The lower-bound argument is given above. The upper bound follows from a pebbling
of an integer multiplication circuit to multiply
n
-bit binary integers
u
and
v
.Thecircuitis
based on the following standard expansion of their product:
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
To construct a circuit we use the observation that the number of 1s in the
j
th column is the
j
th component,
w
j
, of the convolution
w
=
u
v
.(SeeSection
6.7.4
.)
To c omp u t e
w
j
we use the counting circuit
f
(
n
)
⊗
→B
log
n
of Section
2.11
on
n
inputs to count the number of 1s among the products
u
r
v
s
of the Boolean variables
u
r
and
v
s
in the sum
n
count
:
B
w
j
=
r
+
s
=
j
u
r
∗
v
s
for 0
≤
j
≤
2
n
−
2
To c omp u t e t h e 2
n
-bit product we add the binary representations for
w
0
,
w
1
,
...
,
w
2
n−
2
in a set of
(
2
n
1
)
ripple adders, adding
w
j
to the sum
σ
(
j
)=
0
≤i≤j−
1
w
i
2
i
,as
suggested in Fig.
10.7
, where we omit the counting circuits used to compute the values of
w
0
,
...
,
w
2
n−
2
.
−
Search WWH ::
Custom Search