Information Technology Reference
In-Depth Information
is
y
i
. The same holds for all twice continuously differentiable functions whether increasing,
decreasing, convex, or concave in the neighborhood of a zero. It follows that the recurrence
h
(
y
i
)
h
(
y
i
)
y
i
+
1
=
y
i
−
(2.11)
provides values increasingly close to the zero of
h
as long as it is started with a value sufficiently
close to the zero.
The function
h
(
y
)=
1
2
2
n
/uy
has zero
y
=
2
2
n
/u
.Since
h
(
y
)=
2
2
n
/uy
2
,the
−
recurrence (
2.11
) becomes
uy
i
/
2
2
n
When this recurrence is modified as follows, it converges to the
(
n
+
2
)
-bit binary reciprocal
of the
n
-bit binary number
u
:
y
i
+
1
=
2
y
i
−
y
i
+
1
=
2
2
n
+
1
y
i
−
uy
i
2
2
n
The size and depth of a circuit resulting from this recurrence are
O
(
M
int
(
n
,
c
)log
n
)
and
O
(log
2
n
)
, respectively. However, this recurrence uses more gates than are necessary since it
does calculations with full precision at each step even though the early steps use values of
y
i
that are imprecise. We can reduce the size of the resulting circuit to
O
(
M
int
(
n
,
c
))
if, instead
of computing the reciprocal with
n
+
2 bits of accuracy at every step we let the amount of
accuracy vary with the number of stages, as in the algorithm
recip(
u
,
n
)
of Fig.
2.20
.The
algorithm
recip
is called 1
+log
2
n
times, the last time when
n
=
1.
We now show that the algorithm
recip(
u
,
n
)
computes the function
f
(
n
)
recip
(
u
)=
r
=
2
2
n
/u
. In other words, we show that
r
satisfies
ru
=
2
2
n
−
s
for some 0
≤
s<u
.The
proof is by induction on
n
.
The inductive hypothesis is that the algorithm
recip(
u
,
m
)
produces an
(
m
+
2
)
-bit
approximation to the reciprocal of the
m
-bit binary number
u
(whose most significant bit is
1), that is, it computes
r
=
2
2
m
/u
. The assumption applies to the base case of
m
=
1since
u
=
1and
r
=
4. We assume it holds for
m
=
n/
2 and show that it also holds for
m
=
n
.
Algorithm
recip(
u
,
n
)
if
n
=
1
then
r:=4;
else begin
t:=
recip(
u/
2
n/
2
,
n/
2
)
;
r
:=
(
2
3
n/
2
+
1
t
ut
2
)
/
2
n
;
for
j
:=
3
downto
0
do
if
(
u
(
r
+
2
j
)
−
2
2
n
)
then
r
:=
r
+
2
j
≤
;
end;
return
(
r
);
Figure 2.20
An algorithm to compute
r
,the
(
n
+
2
)
-bit approximation to the reciprocal of the
n
-bit binary number
u
representing the integer
u
,thatis,
r
=
f
(
n
)
recip
(
u
).
Search WWH ::
Custom Search