loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
15th IEEE Symposium on Computer Arithmetic (ARITH-15 '01)
Improved Table Lookup Algorithms for Postscaled Division
Vail, Colorado
June 11-June 13
ISBN: 0-7695-1150-3
David W. Matula, Southern Methodist University
Abstract: Postscaled division is a non-iterative algorithm delivering a quotient of single precision accuracy by the three term product (x\hat y)c and of double precision accuracy by the formula [(x\hat y)c][2 - (y\hat y)c]. Here x is the dividend, \hat y is a low order part complemented form of the divisor y, and c is a table lookup value approximating a "reciprocal function" 1=(y\hat y) to a precision of over 27 bits. Table lookup latency is hidden by performing the lookup in parallel with the first multiplication (x\hat y), with the second multiplication the "postscaling" by the lookup function value. Our contribution herein is the description of two new lookup algorithms for approximating the reciprocal function {1\over y\hat y} 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\over y\hat y} 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.
Citation:
David W. Matula, "Improved Table Lookup Algorithms for Postscaled Division," arith, pp.0101, 15th IEEE Symposium on Computer Arithmetic (ARITH-15 '01), 2001
Usage of this product signifies your acceptance of the Terms of Use.