Information Technology Reference
In-Depth Information
THEOREM
2.9.2
The binary multiplication function
f
(
n
)
mult
2
n
for
n
-bit binary
numbers can be realized by carry-save addition by a circuit of the following size and depth over
the basis
Ω=
2
n
:
B
→B
{∧
,
∨
,
⊕}
:
C
Ω
f
(
n
)
mult
2
)+
C
Ω
f
(
2
n
)
add
≤
5
(
2
n
−
1
)(
n
−
D
Ω
f
(
n
)
mult
3
s
+
D
Ω
f
(
2
n
)
add
≤
where
s
, the number of carry-save adder stages, satisfies
log
2
n
log
2
(
3
/
2
)
+
1
It follows from this theorem and the results of Theorem
2.7.2
that two
n
-bit binary num-
bers can be multiplied by a circuit of size
O
(
n
2
)
and depth
O
(log
n
)
.
s
≤
2.9.2 Divide-and-Conquer Multiplication
We now examine a multiplier of much smaller circuit size but depth
O
(log
2
n
)
. tusesa
divide-and-conquer
technique. We represent two positive integers by their
n
-bit binary num-
bers
u
and
v
. We assume that
n
is even and decompose each number into two
(
n/
2
)
-bit
numbers:
u
=(
u
h
,
u
l
)
,
v
=(
v
h
,
v
l
)
where
u
h
,
u
l
,
v
h
,
v
l
are the high and low components of the vectors
u
and
v
, respectively.
Then we can write
2
n/
2
+
|
u
|
=
|
u
h
|
|
u
l
|
2
n/
2
+
|
v
|
=
|
v
h
|
|
v
l
|
from which we have
)
2
n/
2
+
2
n
|
u
||
v
|
=
|
u
l
||
v
l
|
+(
|
u
h
||
v
h
|
+(
|
v
h
|−|
v
l
|
)(
|
u
l
|−|
u
h
|
)+
|
u
l
||
v
l
|
|
u
h
||
v
h
|
It follows from this expression that only three integer multiplications are needed, namely
|
u
l
||
u
l
|
|
u
h
||
u
h
|
|
v
h
|−|
v
l
|
|
u
l
|−|
u
h
|
)
; multiplication by a power of 2 is done by
realigning bits for addition. Each multiplication is of
(
n/
2
)
-bit numbers. Six additions and
subtractions of 2
n
-bit numbers suffice to complete the computation. Each of the additions
and subtractions can be done with a linear number of gates in logarithmic time.
If
C
(
n
)
and
D
(
n
)
are the size and depth of a circuit for integer multiplication realized
with this divide-and-conquer method, then we have
,
,and
(
)(
C
(
n
)
≤
3
C
(
n/
2
)+
cn
(2.9)
D
(
n
)
≤
D
(
n/
2
)+
d
log
2
n
(2.10)
where
c
and
d
are constants of the construction. Since
C
(
1
)=
1and
D
(
1
)=
1(oneuse
of
AND
suffices), we have the following theorem, the proof of which is left as an exercise (see
Problem
2.28
).
Search WWH ::
Custom Search