Fast division algorithm for binary numbers

Question

I am currently creating a 16-bit ALU using Logisim (i.e. only logical), and I am fixated on the division process. Currently, I just use a simple standard "separation algorithm loop" (as shown below):

• Reading input values;
• Compare input values. Wait until the comparison process is complete;
• If A <B goes to step 10. If A & ge; B, go to the next step;
• Subtract B from A;
• Wait until the subtraction process is complete;
• Add it for counting;
• Wait until the counting process is complete;
• Enter a value from the subtraction process to enter;
• Go to step 1;
• The answer is counter balance A

This, however, takes a lot of time for processes with large responses (repeating a cycle of 300 ticks 65,000 times is not fun). I'm just wondering if there are similar algorithms that are faster (which use only addition and / or subtraction and / or multiplication and any logical logic) that can be implemented using logical gates. Any help or ideas would be greatly appreciated! Fraser

Answer 1

Use long-division . There is no multiplication in the binary expression, since the factor at each bit position can be only 1 or 0. Thus, it can be realized as conditional subtraction (subtract if the result is non-negative) and shift.

This is just a crude scheme, of course.

Answer 2

A typical approach for dividing 32/16: 16 + 16 would be to have dividends stored in a pair of 16-bit registers (which are updated during operation), and the divisor in its own register (which is not). Sixteen times, subtract the top 17 bits of the dividend from the divider; if the borrowing results, discard the result and shift the divider, leaving one place, putting 0 in lsb. If there are no borrowing results, save the result in the divider by moving it to the left, and put 1 in lsb. After sixteen such steps, the lower 16 bits of the dividend register will hold the factor, and the upper 16 bits will contain the remainder. Please note that this operation will only work if the quotient is representable in 16 bits. Please also note that on a processor that thus implements 32/16: 16 + 16 separation, it is convenient to divide arbitrarily large numbers into a 16-bit value, since the top 16 bits of dividends for each step should be the rest of the previous step .