Information Technology Reference
In-Depth Information
THEOREM
2.9.3
If
n
=
2
k
, the binary multiplication function
f
(
n
)
mult
2
n
for
n
-bit
binary numbers can be realized by a circuit for the divide-and-conquer algorithm of the following
size and depth over the basis
Ω=
2
n
:
B
→B
{∧
,
∨
,
⊕}
:
mult
=
O
3
log
2
n
=
O
n
log
2
3
D
Ω
f
(
n
)
C
Ω
f
(
n
)
mult
=
O
(log
2
n
)
The size of this divide-and-conquer multiplication circuit is
O
(
n
1
.
585
)
, which is much
smaller than the
O
(
n
2
)
bound based on carry-save addition. The depth bound can be reduced
to
O
(log
n
)
through the use of carry-save addition. (See Problem
2.29
.) However, even faster
multiplication algorithms are known for large
n
.
2.9.3 Fast Multiplication
Schonhage and Strassen [
303
] have described a circuit to multiply integers represented in
binary that is asymptotically small and shallow. Their algorithm for the multiplication of
n
-bit
binary numbers uses
O
(
n
log
n
log log
n
)
gates and depth
O
(log
n
)
. It illustrates the point
that a circuit can be devised for this problem that has depth
O
(log
n
)
and uses a number of
gates considerably less than quadratic in
n
. Although the coefficients on the size and depth
bounds are so large that their circuit is not practical, their result is interesting and motivates
the following definition.
DEFINITION
2.9.1
M
int
(
n
,
c
)
is the size of the smallest circuit for the multiplication of two
n
-bit
binary numbers that has depth at most
c
log
2
n
for
c>
0
.
The Schonhage-Strassen circuit demonstrates that
M
int
(
n
,
c
)=
O
(
n
log
n
log log
n
)
for
all
n
1. It is also clear that
M
int
(
n
,
c
)=Ω(
n
)
because any multiplication circuit must
examine each component of each binary number and no more than a constant number of
inputs can be combined by one gate. (Chapter
9
provides methods for deriving lower bounds
on the size and depth of circuits.)
Because we use integer multiplication in other circuits, it is convenient to make the follow-
ing reasonable assumption about the dependence of
M
int
(
n
,
c
)
on
n
. We assume that
≥
M
int
(
dn
,
c
)
≤
dM
int
(
n
,
c
)
for all
d
satisfying 0
≤
d
≤
1. This condition is satisfied by the Schonhage-Strassen circuit.
2.9.4 Very Fast Multiplication
If integers in the set
are represented by the exponents of primes in their
prime factorization, they can be multiplied by adding exponents. The largest exponent on a
prime in this range is at most
log
2
N
. Thus, exponents can be represented by
O
(log log
N
)
bits and integers multiplied by circuits with depth
O
(log log log
N
)
. (See Problem
2.32
.)
This depth is much smaller than
O
(log log
N
)
, the depth of circuits to add integers in any
fixed radix system. (Note that if
N
=
2
n
,
log
2
log
2
N
=log
2
n
.) However, addition is very
difficult in this number system. Thus, it is a fast number system only if the operations are
limited to multiplications.
{
0, 1,
...
,
N
−
1
}
Search WWH ::
Custom Search