Information Technology Reference
In-Depth Information
Let
u
1
and
u
0
be the integers corresponding to the most and least significant
n/
2bits
respectively of
u
,thatis,
u
=
u
1
2
n/
2
+
u
0
.Since2
n−
1
≤
u<
2
n
,2
n/
2
−
1
≤
u
1
<
2
n/
2
.Also,
u
2
n/
2
2
n
/u
1
=
u
1
. By the inductive hypothesis
t
=
is the value returned by
recip(
u
1
,
n/
2
)
;thatis,
u
1
t
=
2
n
s
s
<u
1
.Let
w
=
2
3
n/
2
+
1
t
−
≤
−
ut
2
.
for some 0
Then
uw
=
2
2
n
+
1
u
1
t
+
2
3
n/
2
+
1
u
0
t
[
t
(
u
1
2
n/
2
+
u
0
)]
2
−
Applying
u
1
t
=
2
n
s
, dividing both sides by 2
n
, and simplifying yields
−
s
−
2
n/
2
2
uw
2
n
tu
0
=
2
2
n
−
(2.12)
We now show that
uw
2
n
≥
2
2
n
−
8
u
(2.13)
by demonstrating that
(
s
−
tu
0
/
2
n/
2
)
2
8
u
.Wenotethat
s
<u
1
<
2
n/
2
, which implies
≤
(
s
)
2
<
2
n/
2
u
1
≤
u
.Also,since
u
1
t
=
2
n
s
or
t
2
n
/u
1
we have
−
≤
tu
0
2
n/
2
2
<
2
n/
2
u
0
u
1
<
2
n/
2
+
1
2
2
≤
8
u
2
n/
2
−
1
,
u
0
<
2
n/
2
,and2
n−
1
since
u
1
≥
≤
u
. The desired result follows from the observation
that
(
a
−
b
)
2
≤
max (
a
2
,
b
2
)
.
w/
2
n
Since
r
=
, it follows from (
2.13
)that
ur
=
u
w
2
n
>u
w
1
=
uw
2
2
n
2
n
−
2
n
−
u
≥
−
9
u
It follows that
r>
(
2
2
n
/u
)
2
2
n
/u
. The three-step
adjustment process at the end of
recip(
u
,
m
)
increases
ur
by the largest integer multiple of
u
less than 16
u
that keeps it less than or equal to 2
2
n
.Thatis,
r
satisfies
ur
=
2
2
n
−
9. Also from (
2.12
), we see that
r
≤
−
s
for
s<u
, which means that
r
is the reciprocal of
u
.
The algorithm for
recip(
u
,
n
)
translates into a circuit as follows: a)
recip(
u
,1
)
is
realized by an assignment, and b)
recip(
u
,
n
)
,
n>
1, is realized by invoking a circuit for
recip(
≤
some 0
,
n/
2
)
followed by a circuit for
(
2
3
n/
2
+
1
t
ut
2
)
/
2
n
and one to implement
u
2
n/
2
−
u
2
n/
2
the three-step adjustment. The first of these steps computes
, which does not require
any gates, merely shifting and discarding bits. The second step requires shifting
t
left by 3
n/
2
places, computing
t
2
and multiplying it by
u
, subtracting the result from the shifted version
of
t
, and shifting the final result right by
n
places and discarding low-order bits. Circuits for
this have size
cM
int
(
n
,
c
)
for some constant
c>
0anddepth
O
(log
n
)
.Thethirdstepcanbe
done by computing
ur
, adding
u
2
j
for
j
=
3, 2, 1, or 0, and comparing the result with 2
2
n
.
The comparisons control whether 2
j
is added to
r
or not. The one multiplication and the
additions can be done with circuits of size
c
M
int
(
n
,
c
)
for some constant
c
>
0anddepth
O
(log
n
)
. The comparison operations can be done with a constant additional number of gates
and constant depth. (See Problem
2.19
.)
It follows that
recip
can be realized by a circuit whose size
C
recip
(
n
)
is no more than a
multiple of the size of an integer multiplication circuit,
M
int
(
n
,
c
)
, plus the size of a circuit for
Search WWH ::
Custom Search