Improved table lookup algorithms for postscaled division
David W. Matula · 2002
Postscaled division is a non-iterative algorithm delivering a quotient of single precision accuracy by the three term product (xy/spl circ/)c and of double precision accuracy by the formula [(xy/spl circ/)c][2-(yy/spl circ/)c]. Here x is the dividend, y/spl circ/ is a low order part complemented form of the divisor y, and c is a table lookup value approximating a "reciprocal function" 1/(yy/spl circ/) to a precision of over 27 bits. Table lookup latency is hidden by performing the lookup in parallel with the first multiplication (xy/spl circ/), with the second multiplication the "postscaling" by the lookup function value. Our contribution is the description of two new lookup algorithms for approximating the reciprocal function 1/yy/spl circ/ to high accuracy in fewer cycles than a typical floating point multiply latency. Our indirect bipartite lookup procedure has a latency of two successive lookups followed by a small integer addition. This first algorithm generates a 27 bit approximation of 1/yy/spl circ/ with total table size about 5 Kbytes. Our second lookup algorithm generates a 34 bit approximation with latency determined by 11 and 12 bit table lookups and a 4-1 addition. This second approximation employs some 20 Kbytes of tables to allow for a double extended precision division result in the same number of cycles as a double precision result.