Binary divider circuit (brute-force using counters)

Thread Starter

128ITSH

Joined Jul 20, 2017
101
Hello everyone!

I was searching for a binary division circuit using logic gates or simple 4000/7400 logic IC's, but all I found were algorithms for binary division - not circuits.
So I wondered if such circuit can be made with a divide-by-N counter and came up with this circuit:



The top left counter is loaded with the dividend and counts down until it reaches 0 count. when that happens, the R-S latch is reset and counting is stopped in all counters so the number of pulses that went to the divisor counter (upper right) equals the dividend.
The upper right counter is used as a divide-by-N counter that outputs one clock pulse for every N pulses on it's clock input (N=divisor input).
The output of this counter is connected to the clock input of the bottom right counter that counts up, and by that counts up to get the quotient.
The bottom left counter counts up with the same clock of the divisor and dividend counters, but gets reset on every division, and in the end of the count outputs the remainder


What do you think about this design? do you know any other way to divide numbers with digital logic?
 

Attachments

GopherT

Joined Nov 23, 2012
8,009
Hello everyone!

I was searching for a binary division circuit using logic gates or simple 4000/7400 logic IC's, but all I found were algorithms for binary division - not circuits.
So I wondered if such circuit can be made with a divide-by-N counter and came up with this circuit:



The top left counter is loaded with the dividend and counts down until it reaches 0 count. when that happens, the R-S latch is reset and counting is stopped in all counters so the number of pulses that went to the divisor counter (upper right) equals the dividend.
The upper right counter is used as a divide-by-N counter that outputs one clock pulse for every N pulses on it's clock input (N=divisor input).
The output of this counter is connected to the clock input of the bottom right counter that counts up, and by that counts up to get the quotient.
The bottom left counter counts up with the same clock of the divisor and dividend counters, but gets reset on every division, and in the end of the count outputs the remainder


What do you think about this design? do you know any other way to divide numbers with digital logic?

Nope, that is how I have done it. Both in digital logic chips and 8-bit microcontrollers.
 

WBahn

Joined Mar 31, 2012
29,979
How does such an solution implement for 16-, 32-, or 64-bit inputs? Not well at all -- it's exponential in the number of bits in the dividend.

A far more efficient algorithm is to do it essentially the same way you would do it by hand -- i.e., long division.

Initialize a quotient register to 0 and a place flag to 1. Shift the divisor to the left until it is strictly larger than the dividend, then shift to the right one place. Do the same operations on the shift flag. This flag will track the corresponding bit place in the quotient. Subtract the divisor from the dividend and bitwise OR the place flag with the quotient. Shift the divisor (and the place flag) to the right until the divisor is no longer greater than the shifted quantity from the dividend. Subtract the divisor from the dividend and keep repeating this until the place flag becomes zero. The quotient is now set and the dividend register now holds the remainder. You can tweak this algorithm to use the same registers since as msb bits are cleared they can be used to hold the new bits of the quotient.
 

Thread Starter

128ITSH

Joined Jul 20, 2017
101
How does such an solution implement for 16-, 32-, or 64-bit inputs? Not well at all -- it's exponential in the number of bits in the dividend.
By exponential, do you mean that the clock pulses needed to set the dividend down to zero will be too much? If so you're right, a 2^64 number is really too big for this operation and even with several Ghz clock it will take some years to divide it.
However, I would use this solution for things like home-brew 8-bit computers (which by the way I'm working on right now, but will not support division).

A far more efficient algorithm is to do it essentially the same way you would do it by hand -- i.e., long division.

Initialize a quotient register to 0 and a place flag to 1. Shift the divisor to the left until it is strictly larger than the dividend, then shift to the right one place. Do the same operations on the shift flag. This flag will track the corresponding bit place in the quotient. Subtract the divisor from the dividend and bitwise OR the place flag with the quotient. Shift the divisor (and the place flag) to the right until the divisor is no longer greater than the shifted quantity from the dividend. Subtract the divisor from the dividend and keep repeating this until the place flag becomes zero. The quotient is now set and the dividend register now holds the remainder. You can tweak this algorithm to use the same registers since as msb bits are cleared they can be used to hold the new bits of the quotient.
This solution is interesting but its hard for me to understand it this way, Can you refer me to a more visual explanation/example?
 

WBahn

Joined Mar 31, 2012
29,979
This solution is interesting but its hard for me to understand it this way, Can you refer me to a more visual explanation/example?
How do you divide 341 into 75687? It's basically the same steps, only you need to be a bit more explicit than humans tend to be when we do it because we internalize some of the steps and don't even think about it.

So start with a flag value initialized to 1 and a quotient initialized to 0.

flag = 1; quotient = 0;

Now move the flag quotient over one place by multiplying by 10 and multiplying the divisor by 10 in lock step with it until the divisor is greater than the dividend. As soon as it is, you are ready to proceed.

341 > 75687? N => flag = 10 divisor = 3410
3410 > 75687? N => flag = 100 divisor = 34100
34100 > 75687? N => flag = 1000 divisor = 341000
341000 > 75687? Y => DONE

Now see how many times your divisor will go into dividend by subtracting it repeatedly until the dividend is smaller than the divisor. At each step, add the flag to the quotient. Once it is smaller, move the flag over by dividing both it and the dividend by ten. Repeat this cycle until the flag becomes 0.

flag > 0? Y => dividend = 341000 / 10 = 34100
75687 < 34100? N => dividend = 75687 - 34100 = 41587; quotient = 0 + 100 = 100
41587 < 34100? N => dividend = 41587 - 34100 = 7487; quotient = 100 + 100 = 200
7487 < 34100? Y => flag = 100 / 10 = 10;
flag > 0? Y => dividend = 34100 / 10 = 3410
7487 < 3410? N => dividend = 7487 - 3410 = 4077; quotient = 200 + 10 = 210
4077 < 3410? N => dividend = 4077 - 3410 = 667; quotient = 210 + 10 = 220
667 < 3410? Y => flag = 10 / 10 = 1;
flag > 0? Y => dividend = 3410 / 10 = 341
667 < 341? N => dividend = 667 - 341 = 326; quotient = 220 + 1 = 221
326 < 341? Y => flag = 1 / 10 = 0
flag > 0? N

Now the quotient is set to 221 and the remainder is the value stored in the dividend, which is 326.

Let's check the result: 221 * 341 + 326 = 75687

Quite a bit fewer steps than the 75000+ iterations needed by your proposed approach.

Because your homebrew computer is going to be very limited and very slow, you NEED to look for and implement extremely efficient algorithms to compensate.

Implementing this algorithm in binary makes it a LOT simpler. Instead of multiplying and dividing by 10, you need to multiply and divide by 2, which is really easy since multiplying by 2 is just a left bit shift and dividing by 2 is just a right bit shift. You also don't have to check to see how many times you need to subtract the divisor from the quotient since each time is it no longer greater than the dividend, you must subtract it exactly once.

So try to see if you can figure out the binary algorithm is use it to divide 75687 (10010011110100111) by 341 (101010101). It's only going to take about eight iterations.
 

Thread Starter

128ITSH

Joined Jul 20, 2017
101
How do you divide 341 into 75687? It's basically the same steps, only you need to be a bit more explicit than humans tend to be when we do it because we internalize some of the steps and don't even think about it.

So start with a flag value initialized to 1 and a quotient initialized to 0.

flag = 1; quotient = 0;

Now move the flag quotient over one place by multiplying by 10 and multiplying the divisor by 10 in lock step with it until the divisor is greater than the dividend. As soon as it is, you are ready to proceed.

341 > 75687? N => flag = 10 divisor = 3410
3410 > 75687? N => flag = 100 divisor = 34100
34100 > 75687? N => flag = 1000 divisor = 341000
341000 > 75687? Y => DONE

Now see how many times your divisor will go into dividend by subtracting it repeatedly until the dividend is smaller than the divisor. At each step, add the flag to the quotient. Once it is smaller, move the flag over by dividing both it and the dividend by ten. Repeat this cycle until the flag becomes 0.

flag > 0? Y => dividend = 341000 / 10 = 34100
75687 < 34100? N => dividend = 75687 - 34100 = 41587; quotient = 0 + 100 = 100
41587 < 34100? N => dividend = 41587 - 34100 = 7487; quotient = 100 + 100 = 200
7487 < 34100? Y => flag = 100 / 10 = 10;
flag > 0? Y => dividend = 34100 / 10 = 3410
7487 < 3410? N => dividend = 7487 - 3410 = 4077; quotient = 200 + 10 = 210
4077 < 3410? N => dividend = 4077 - 3410 = 667; quotient = 210 + 10 = 220
667 < 3410? Y => flag = 10 / 10 = 1;
flag > 0? Y => dividend = 3410 / 10 = 341
667 < 341? N => dividend = 667 - 341 = 326; quotient = 220 + 1 = 221
326 < 341? Y => flag = 1 / 10 = 0
flag > 0? N

Now the quotient is set to 221 and the remainder is the value stored in the dividend, which is 326.

Let's check the result: 221 * 341 + 326 = 75687

Quite a bit fewer steps than the 75000+ iterations needed by your proposed approach.

Because your homebrew computer is going to be very limited and very slow, you NEED to look for and implement extremely efficient algorithms to compensate.

Implementing this algorithm in binary makes it a LOT simpler. Instead of multiplying and dividing by 10, you need to multiply and divide by 2, which is really easy since multiplying by 2 is just a left bit shift and dividing by 2 is just a right bit shift. You also don't have to check to see how many times you need to subtract the divisor from the quotient since each time is it no longer greater than the dividend, you must subtract it exactly once.

So try to see if you can figure out the binary algorithm is use it to divide 75687 (10010011110100111) by 341 (101010101). It's only going to take about eight iterations.
Ok, thank you very much for the explanation. Now I want to implement this in binary, so I will write it in pseudo code:

DWORD placeFlag =0000 0000 0000 0000 0000 0000 0000 0001; //1
DWORD dividend = 0000 0000 0000 0001 0010 0111 1010 0111 //75687;
DWORD divisor = 0000 0000 0000 0000 0000 0001 0101 0101 //341;
DWORD quotient = 0000 0000 0000 0000 0000 0000 0000 0000; //0

while(divisor < dividend) //How can I implement this 'while' check in a logic circuit?
{
divisor << 1; // one shift to the left - should I use parallel in-parallel out left/right shift register for the circuit
flag << 1;
}
while(flag > 0) //how can I implement this loop too?
{
divisor >> 1; // one shift to the right
dividend = dividend - divisor; //subtract divisor from dividend
quotient = quotient + placeFlag;//add placeFlag to quotient
placeFlag >> 1; // one shift to the right
}​

This is all. As you said when it gets to binary this algorithm is very (time) efficient for this purpose. But I want to actually design a logic circuit for this (and maybe use it in my homebrew computer), and I am not sure how to implement this... Can you help me with finding the right logic IC's for this algorithm? I will (hopefully) figure out the rest.
 

WBahn

Joined Mar 31, 2012
29,979
You need to decide if you want this to be sequential or combinatorial. Given your starting point, it sounds like sequential is the way you are leaning, which is probably the easier route. For the while() loop you need to implement the test, A<B. That is a pretty straightforward combinatorial logic circuit, particularly if you have already captured the sign of the result and converted both the dividend and the divisor to unsigned integers.
 
Top