Browse Prior Art Database

Fast Division

IP.com Disclosure Number: IPCOM000046839D
Original Publication Date: 1983-Aug-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 43K

Publishing Venue

IBM

Related People

Galand, C: AUTHOR

Abstract

Digital inversion can be achieved either by straight table-lookup or by iterative algorithms. Assuming a 12-bit arithmetic, the former requires at least a 2048-word table size, if the sign is treated separately. The latter requires 12 iterations, each of them including tests, additions"substractions and set/reset of bits. Such an iterative method has been proposed [*]. Both methods have advantages and drawbacks: - a fast execution time at the price of a large table size for the former, and - a slow execution time and a small table size for the latter. The following algorithm makes a trade-off between these two alternatives, and results in an acceptable execution time for a small table size.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 2

Fast Division

Digital inversion can be achieved either by straight table-lookup or by iterative algorithms. Assuming a 12-bit arithmetic, the former requires at least a 2048-word table size, if the sign is treated separately. The latter requires 12 iterations, each of them including tests, additions"substractions and set/reset of bits. Such an iterative method has been proposed [*]. Both methods have advantages and drawbacks: - a fast execution time at the price of a large

table size for the former, and

- a slow execution time and a small table size for

the latter. The following algorithm makes a trade-off between these two alternatives, and results in an acceptable execution time for a small table size. So as to achieve full 12-bit precision, it is assumed that the input argument X to be inverted is positive and properly normalized, resulting in a normalized value X' within the interval (1024, 2047). (1)X' = X.2NORM for example, if X = '000010101101'

then X'= '010101101000'

and NORM = 3 This normalization step can easily be achieved with a shift register and some random logic. The inversion algorithm thus gives an approximation of: (2) YO = 2048 . 1024 ___________

X' and is based on the fact that when partitionning the interval (1024, 2047) into 16 equal sub-intervals, the difference (YO - A (I) (where A (I) represents the inverse value of the 4 MSBs (most significant bits) of X' and I represents the interval index I = 0,...,15), can be well approximated by a linear function of slope C (I) in each sub-interval I. The figure represents the in...