Browse Prior Art Database

High-Precision Reciprocator

IP.com Disclosure Number: IPCOM000112756D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 148K

Publishing Venue

IBM

Related People

Bowen, AD: AUTHOR [+2]

Abstract

A method for generating the reciprocal of a 16-bit value having a variable number of integer and fractional bits is disclosed. Furthermore, a 16-bit result is produced having a variable binary point, thereby reducing the size of subsequent logic while maintaining the maximum precision of the 16-bit result.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 35% of the total text.

High-Precision Reciprocator

      A method for generating the reciprocal of a 16-bit value having
a variable number of integer and fractional bits is disclosed.
Furthermore, a 16-bit result is produced having a variable binary
point, thereby reducing the size of subsequent logic while
maintaining the maximum precision of the 16-bit result.

      Background - In order to provide perspective correction for
interpolated texture coordinates (or any other interpolated value), a
reciprocation or division is necessary.  For example, the texture
coordinate (s,t) is usually interpolated linearly across an area.  To
account for perspective, (s/w, t/w, 1/w) are interpolated linearly
(where w indicates the relative depth of the vertex).  Once the
interpolated triplet is generated, s/w and t/w are divided by 1/w (or
multiplied by w).  The regeneration of w by reciprocation can require
many bits to account for the very wide range that w can assume.  The
problem to be solved is then to reciprocate a 16-bit input, and
provide 16 bits of output precision, without unnecessary bits in the
result.

      The Solution - The reciprocation is performed using the
Newton-Raphson algorithm.  The input value can be very small,
generating a very large reciprocal, or very close to unity, producing
a reciprocal with many significant fraction bits.  The Newton-Raphson
iteration is defined as:

                     'X' sub 'n'+1 = 'X' sub 'n' -
        <f%('X' sub 'n')> over <f sup <% prime> ('X' sub 'n')>

To find <1 over 'x'>, an equation with a single root at <1 over 'x'>
should be used.  Using a = <1 over 'x'>, or xinv - 'a' = 0, the
derivative 'd' over 'dx' of this function is lb < -'x' **-2 > rb.
Thus,

X sub n+1 = X sub n - < X sub n ** %-1 - a > over < -X sub n ** %-2 >

Multiplying by  <'X' sub 'n' ** 2> over <'X' sub 'n' ** 2>:

          X sub n+1 = X sub n + lb < X sub n - aX sub n ** 2 > rb
 or

               X sub n+1 = X sub n * lb < 2 - aX sub n > rb

      The flow of the Newton-Raphson Reciprocator is shown in the
Figure.  <1 over 'w'>  is passed to NRR2 as the X input.  In order to
maximize precision, a floating-point-like method is used-  the
leading zeros of the input are removed and the exponent is maintained
separately.  After X is shifted left, the value to be reciprocated is
between 0.8000[16]  and 0.FFFF[16], making the result in the range of
1.0000 and  1.FFFC[16].  (The reciprocal of 0.8000[16]  is 2.0, but
is special cased to be 1.0 and the exponent is incremented by 1.)
The first step of the reciprocator performs the left-alignment of the
data.  A leading-one detector determines the amount of left-shift
required.  The leading-one position (L1) is the bit position of the
most significant '1'.  For example, the leading-one position of
0x4000  is 1.  If the input is 0x0000  (indicating a very small
number) the leading-one detector returns -1 (L1=0b1 1111).  Th...