Information Technology Reference
In-Depth Information
2.9.5 Reductions to Multiplication
The logical shifting function
f
(
n
)
shift
can be reduced to integer multiplication function
f
(
n
)
mult
,as
can be seen by letting one of the two
n
-tuple arguments be a power of 2. That is,
f
(
n
)
mult
(
x
,
y
)
f
(
n
)
shift
(
x
,
s
)=
π
(
n
)
L
where
y
=
f
(
m
)
decode
(
s
)
is the value of the decoder function (see Section
2.5
)thatmapsabinary
m
-tuple,
m
=
, into a binary 2
m
-tuple containing a single 1 at the output indexed
by the integer represented by
s
and
π
(
n
)
L
log
2
n
is the projection operator defined on page
50
.
LEMMA
2.9.1
The logical shifting function
f
(
n
)
shift
can be reduced to the binary integer multipli-
cation function
f
(
n
)
mult
through the application of the decoder function
f
(
m
)
decode
on
m
=
log
2
n
inputs.
AsshowninSection
2.5
, the decoder function
f
(
m
)
decode
can be realized with a circuit of size
very close to 2
m
and depth
. Thus, the shifting function has circuit size and depth
no more than constant factors larger than those for integer multiplication.
The
squaring function
f
(
n
)
log
2
m
2
n
maps the binary
n
-tuple
x
into the binary
2
n
-tuple
y
representing the product of
x
with itself. Since the squaring and integer multipli-
cation functions contain each other as subfunctions, as shown below, circuits for one can be
used for the other.
n
square
:
B
→B
LEMMA
2.9.2
The integer multiplication function
f
(
n
)
contains the squaring function
f
(
n
)
square
mult
as a subfunction and
f
(
3
n
+
1
)
square
contains
f
(
n
)
mult
as a subfunction.
Proof
The first statement follows by setting the two
n
-tuple inputs of
f
(
n
)
mult
to be the input
to
f
(
n
)
square
. The second statement follows by examining the value of
f
(
3
n
+
1
)
square
on the
(
3
n
+
1
)
-
tuple input
(
xzy
)
,where
x
and
y
are binary
n
-tuples and
z
is the zero binary
(
n
+
1
)
-tuple.
Thus,
(
xzy
)
denotes the value
a
=
2
2
n
+
1
|
x
|
+
|
y
|
whose square
b
is
b
=
2
4
n
+
2
2
+
2
2
n
+
2
2
|
x
|
|
x
||
y
|
+
|
y
|
|
x
||
y
|
Thevalueoftheproduct
can be read from the output because there is no carry
into 2
2
n
+
2
2
,noristhereacarryinto2
4
n
+
2
from 2
2
n
+
2
|
x
||
y
|
|
y
|
|
x
|
2
|
x
||
y
|
from
,since
2
n
|
x
|
|
y
|≤
−
,
1.
2.10 Reciprocal and Division
In this section we examine methods to divide integers represented in binary. Since the division
of one integer by another generally cannot be represented with a finite number of bits (consider,
for example, the value of 2
/
3), we must be prepared to truncate the result of a division. The
division method presented in this section is based on Newton's method for finding a zero of a
function.
Let
u
=(
u
n−
1
,
...
,
u
1
,
u
0
)
and
v
=(
v
n−
1
,
...
,
v
1
,
v
0
)
denote integers whose magni-
tudes are
u
and
v
. Then the division of one integer
u
by another
v
,
u/v
, can be obtained as the
Search WWH ::
Custom Search