13th IEEE Symposium on Computer Arithmetic (ARITH-13 '97)
Faithful Interpolation in Reciprocal Tables
Asilomar, CA
March 06-March 09
ISBN: 0-8186-7846-1
We describe a table compression method employing finite precision linear interpolation in reciprocal tables. The interpolation method employs a compressed look-up table and a small sized multiplier to yield an output reciprocal as a simple direct operation. The leading bits of the arbitrarily precise input are used to index the table and a limited number of succeeding fractional bits are used to interpolate on the table employing a multiply/add operation. The low order bits of the product are rounded off so the output reciprocals are guaranteed correct to a unit in the last place, and provide a round-to-nearest reciprocal for over 90% of arbitrarily precise input arguments. The interpolation method generates 2k-bit faithful reciprocals employing a k-bits-in 2k+2-bits-out table and a (k+3) X (k+3) bit multiplier. A single precision faithful reciprocal can be generated employing a table of size 13 Kbytes and a 15 X 15 bit multiplier, compared to a table size of 46 Mbytes for conventional reciprocal tables. The table and dedicated small multiplier efficiently characterize a functional reciprocator unit with at most a couple of cycle latency.