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