Division algorithms and implementations
- 1 August 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 46 (8) , 833-854
- https://doi.org/10.1109/12.609274
Abstract
Many algorithms have been developed for implementing division in hardware. These algorithms differ in many aspects, including quotient convergence rate, fundamental hardware primitives, and mathematical formulations. The paper presents a taxonomy of division algorithms which classifies the algorithms based upon their hardware implementations and impact on system design. Division algorithms can be divided into five classes: digit recurrence, functional iteration, very high radix, table look-up, and variable latency. Many practical division algorithms are hybrids of several of these classes. These algorithms are explained and compared. It is found that, for low-cost implementations where chip area must be minimized, digit recurrence algorithms are suitable. An implementation of division by functional iteration can provide the lowest latency for typical multiplier latencies. Variable latency algorithms show promise for simultaneously minimizing average latency while also minimizing area.Keywords
This publication has 45 references indexed in Scilit:
- An accurate, high speed implementation of division by reciprocal approximationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A 17 × 69 bit multiply and add unit with redundant binary feedback and single cycle latencyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Faithful interpolation in reciprocal tablesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Rounding for quadratically converging algorithms for division and square rootPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- 167 MHz radix-8 divide and square root using overlapped radix-2 stagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Accurate rounding scheme for the Newton-Raphson method using redundant binary representationIEEE Transactions on Computers, 1994
- Performance features of the PA7100 microprocessorIEEE Micro, 1993
- Fast division using accurate quotient approximations to reduce the number of iterationsIEEE Transactions on Computers, 1992
- Computation of elementary functions on the IBM RISC System/6000 processorIBM Journal of Research and Development, 1990
- The IBM System/360 Model 91: Floating-Point Execution UnitIBM Journal of Research and Development, 1967