Fast division algorithm for binary numbers

Question

I'm currently building a 16 bit ALU using Logisim (ie logic gates only), and am stuck on a division process. I am currently just using the simple standard "division algorithm loop" (as shown below):

1. Read input values;
2. Compare input values. Wait until comparison process has finished;
3. If A<B go to step 10. If A≥B, go to next step;
4. Subtract B from A;
5. Wait until subtraction process has finished;
6. Add one to count;
7. Wait until counting process has finished;
8. Write value from subtraction process to input;
9. Go to step 1;
10. Answer is count remainder A

This, however, takes a very long time for processes with large answers (repeating a 300 tick cycle 65,000 times isn't fun). I'm just wondering if there are similar algorithms which are quicker (that exclusively use addition and/or subtraction and/or multiplication and any boolean logic) that could be implemented using logic gates. Any help or ideas would be greatly appreciated! Fraser

Answer 1

Use long-division. In binary, there is no multiplication, since the quotient at each bit position can only be 1 or 0. So it can be implemented as a conditional subtract (subtract if result non-negative) and shift.

That's just a crude outline, of course.

Answer 2

A typical approach for a 32/16:16+16 division would be to have the dividend stored in a pair of 16-bit registers (which get updated during operation) and the divisor in its own register (which doesn't). Sixteen times, subtract the upper 17 bits of the dividend from the divisor; if a borrow results, discard the result and shift the divisor left one place, putting a 0 into the lsb. If no borrow results, store the result into the divisor while shifting it left, but put a 1 into the lsb. After sixteen such steps, the lower 16 bits of the dividend register will hold the quotient, and the upper 16 bits will hold the remainder. Note that this operation will only work if the quotient is representable in 16 bits. Note also that on a processor which implements 32/16:16+16 division in this fashion, one may conveniently divide arbitrarily-large numbers by a 16-bit quantity, since the upper 16 bits of dividend for each step should be the remainder from the previous step.