A New Algorithm for Division in Hardware


Prof. Vitit Kantabutra presented a new "subtractive" division algorithm (more correctly: class of algorithms) for implementation in hardware at the 1996 International Conference on Computer Design in Austin, Texas. This algorithm allows at least 2 dividend bits to be retired per full-precision addition (or subtraction), but is much simpler than traditional Radix-4 SRT algorithms. In particular, the new algorithm requires no lookup table (e.g., PLA), and only requires one 2-bit comparison operation plus some simple additional logic per iteration.

The algorithm presented at the conference can be extended to allow the partial remainder to be kept in redundant form. However, the algorithm becomes more complex (but seemingly still simpler than traditional radix-4 SRT algorithms). It appears at this time that the best implementation of the new algorithm may be with the partial remainder kept in regular binary format, but this is not at all clear, since both the redundant and non-redundant hardware can be tuned to obtain better performance. (Transistor sizing is one of the key techniques for tuning.)

If we keep the partial remainder in non-redundant form and implement the divider as a self-timed circuit, then the circuit will operate very quickly, because the average length of a carry signal in an adder is only a logarithmic function of the operand length. Since there are so many additions to be performed in each division operation, the total delay due to addition should be small.

Kantabutra's new division algorithm appears to be easier to implement correctly than traditional radix-4 SRT algorithms, due to the lack of a lookup table. Such a complex lookup table was the source of the infamous "Intel Pentium Division Bug," the best known computer circuit bug in recent times. Indeed, the Intel bug has generated much research in the field of circuit verification. While recognizing the value of verification, we offer an alternative: use a simpler algorithm to begin with!

Perl code simulating division algorithm


V. Kantabutra, "A New Algorithm for Division in Hardware," Proceedings of the 1996 International Conference on Computer Design, IEEE, Austin, Texas: October, 1996.