Fast division using accurate quotient approximations to reduce the number of iterations
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 41 (8) , 981-995
- https://doi.org/10.1109/12.156541
Abstract
A class of iterative integer division algorithms is presented based on look-up table and 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 components show that this method is faster than the Newton-Raphson technique and can produce 53-b quotients of 53-b numbers in about 25 ns using the basic method and 21 ns using the advanced method. In addition, these methods naturally produce an exact remainder, which is very useful for implementing precise rounding specifications.Keywords
This publication has 13 references indexed in Scilit:
- An 8 ns BiCMOS 1 Mb ECL SRAM with a configurable memory array sizePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- An 8 ns 1 Mb ECL BiCMOS SRAMPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- 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
- 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
- Fast radix-2 division with quotient-digit predictionJournal of Signal Processing Systems, 1989
- High bandwidth evaluation of elementary functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- 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