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