#
A New Algorithm for Division in Hardware

NEW COMPARISON-BASED
RADIX-8 DIVISION ALGORITHMS
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

####
Reference

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