Improved table lookup algorithms for postscaled division

Postscaled division is a non-iterative algorithm delivering a quotient of single precision accuracy by the three term product (xyˆ)c and of double precision accuracy by the formula [(xyˆ)c][2-(yyˆ)c]. Here x is the dividend, yˆ is a low order part complemented form of the divisor y, and c is a table lookup value approximating a “reciprocal function” 1/(yyˆ) to a precision of over 27 bits. Table lookup latency is hidden by performing the lookup in parallel with the first multiplication (xyˆ), 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ˆ 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ˆ 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