DIVISION ALGORITHMS AND IMPLEMENTATIONS

Many algorithms have been developed for implementing division in hardw are. These algorithms differ in many aspects, including quotient conve rgence rate, fundamental hardware primitives, and mathematical formula tions. This paper presents a taxonomy of division algorithms which cla ssifies the algorithms based upon their hardware implementations and i mpact on system design. Division algorithms can be divided into five c lasses: 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 a nd compared in this work. It is found that, for low-cost implementatio ns where chip area must be minimized, digit recurrence algorithms are suitable. An implementation of division by functional iteration can pr ovide the lowest latency for typical multiplier latencies. variable la tency algorithms show promise for simultaneously minimizing average la tency while also minimizing area.