Fast division using accurate quotient approximations to reduce the number of iterations
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A class of iterative integer division algorithms is presented based on lookup table Taylor-series approximations to the reciprocal. The algorithm iterates by using the reciprocal to find an approximate quotient and then subtracting the quotient multiplied by the divisor from the dividend to find a remaining dividend. Fast implementations can produce an average of either 14 or 27 b per iteration, depending on whether the basic or advanced version of this method is implemented. Detailed analyses are presented to support the claimed accuracy per iteration. Speed estimates using state-of-the-art ECL (emitted coupled logic) components show that this method is faster than the Newton-Raphson technique and can produce 53-b quotients of 53-b numbers in about 28 or 22 ns for the basic and advanced versions.Keywords
This publication has 7 references indexed in Scilit:
- Algorithm for high speed shared radix 8 division and radix 8 square rootPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Approaching a nanosecond: a 32 bit adderPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Designing high-performance digital circuits using wave pipelining: algorithms and practical experiencesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Computation of elementary functions on the IBM RISC System/6000 processorIBM Journal of Research and Development, 1990
- Design of the IBM RISC System/6000 floating-point execution unitIBM Journal of Research and Development, 1990
- On Range-Transformation Techniques for DivisionIEEE Transactions on Computers, 1970
- Higher-Radix Division Using Estimates of the Divisor and Partial RemaindersIEEE Transactions on Computers, 1968