Measuring the accuracy of ROM reciprocal tables
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
It is proved that a conventional ROM reciprocal table construction algorithm generates tables that minimize the relative error. The worst case relative errors realized for such optimally computed k-bits-in, m-bits-out ROM reciprocal tables are then determined for all table sizes 3 /spl les/ k, m /spl les/ 12. It is then proved that the table construction algorithm always generates a k-bits-in, k-bits-out table with relative errors never any greater than 3(2/sup -k/)/4 for any k, and, more generally with g guard bits, that for (k + g)-bits-out the relative error is never any greater than 2/sup -(k+1)/(1 + 1/(2/sup g+1/)). To provide for determining test data without prior construction of a full ROM reciprocal table, a procedure that requires generation and searching of only a small portion of such a table to determine regions containing input data yielding the worst case relative errors is described.<>Keywords
This publication has 3 references indexed in Scilit:
- An accurate, high speed implementation of division by reciprocal approximationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Fast division using accurate quotient approximations to reduce the number of iterationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A Division Method Using a Parallel MultiplierIEEE Transactions on Electronic Computers, 1967