Information Technology Reference
In-Depth Information
result of taking the product of
u
with the reciprocal 1
/v
. (See Problem
2.33
.) For this reason,
we examine only the computation of reciprocals of
n
-bit binary numbers. For simplicity we
assume that
n
is a power of 2.
The reciprocal of the
n
-bit binary number
u
=(
u
n−
1
,
...
,
u
1
,
u
0
)
representing the in-
teger
u
is a fractional number
r
represented by the (possibly infinite) binary number
r
=
(
r
−
1
,
r
−
2
,
r
−
3
,
...
)
,where
=
r
−
1
2
−
1
+
r
−
2
2
−
2
+
r
−
3
2
−
3
+
|
r
|
···
Some numbers, such as 3, have a binary reciprocal that has an infinite number of digits, such as
(
0, 1, 0, 1, 0, 1,
...
)
, and cannot be expressed exactly as a binary tuple of finite extent. Others,
such as 4, have reciprocals that have finite extent, such as
(
0, 1
)
.
Our goal is to produce an
(
n
+
2
)
-bit approximation to the reciprocal of
n
-bit binary
numbers. (It simplifies the analysis to obtain an
(
n
+
2
)
-bit approximation instead of an
n
-bit
approximation.) We assume that each such binary number
u
has a 1 in its most significant po-
sition; that is, 2
n−
1
u<
2
n
. If this is not true, a simple circuit can be devised to determine
the number of places by which to shift
u
left to meet this condition. (See Problem
2.25
.) The
result is shifted left by an equal amount to produce the reciprocal.
It follows that an
(
n
+
2
)
-bit approximation to the reciprocal of an
n
-bit binary number
u
with
u
n−
1
=
1 is represented by
r
=(
r
−
1
,
r
−
2
,
r
−
3
,
...
)
,wherethefirst
n
≤
2 digits of
r
are
zero. Thus, the value of the approximate reciprocal is represented by the
n
+
2 components
(
r
−
(
n−
1
)
,
r
−
(
n
)
,
...
,
r
−
(
2
n
)
)
. It follows that these components are produced by shifting
r
left
by 2
n
places and removing the fractional bits. This defines the function
f
(
n
)
−
recip
:
recip
(
u
)=
2
2
n
f
(
n
)
u
The approximation described below can be used to compute reciprocals.
Newton's approximation algorithm
is a method to find the zero
x
0
of a twice contin-
uously differentiable function
h
:
on the reals (that is,
h
(
x
0
)=
0) when
h
has
a non-zero derivative
h
(
x
)
in the neighborhood of
x
0
. As suggested in Fig.
2.19
,theslope
of the tangent to the curve at the point
y
i
,
h
(
y
i
)
,isequalto
h
(
y
i
)
/
(
y
i
−
→
y
i
+
1
)
.Forthe
convex increasing function shown in this figure, the value of
y
i
+
1
is closer to the zero
x
0
than
h
(
x
)
h
(
y
i
)
x
x
0
y
i
+
1
y
i
Figure 2.19
Newton's method for finding the zero of a function.
Search WWH ::
Custom Search