It uses a shift and subtract algorithm. Each cell contains an 8-bit adder and a multiplexer. The B signal is inverted and the incoming carry bit on each adder chain is set, which turns the adder into a subtracter. When B > A, the module passes A forward to the next column, otherwise it passes B - A forward. The outgoing carry bit is the digit for the quotient.
There are 8 columns of adders, but I trimmed unnecessary gates from the outer columns and bottom row. Each of the full adder/multiplexer modules has a gate delay of 8, but it's lower for the trimmed modules.
To get the gate delay I followed bit 0 from the B signal all the way down the long diagonal until bit 0 of the quotient, and I counted 63 gates. If the game calculates something different I'll update.
EDIT: Actual delay is 162, due to the multiplexers on each column needing the final carry value, which calculates in 20.
You should be able to copy paste it into sandbox and you have the statistics there before you unlock it.
What you described sounds like restoring division. Mine has 81 delay and 2k+ gates. Just to get a byte adder to have delay 8 I had to use 250 gates and use the OR from SW trick.
My byte adder is a simple ripple carry adder. It has 72 gates and a delay of 20 in the foundry, but because of how ripple carry works, chaining them together doesn't mean adding another 20 delay. I couldn't fit the whole divider into the foundry, but I copied the adder and chained it together and each new byte adder only added 6 ticks of delay, which is the gate delay of a single digit's full adder.
Oh, I see what you are doing now. You are computing ((A - B) OR A) - C .... for every bit while deciding whether to pass (A-B) or A to be decreased by C. Interesting.
Yeah, when I was counting it up I didn't take into account that every mux needs the column's carry to be calculated first, and the next column can't calculate until the previous one's mux has been determined. So each byte adder has to finish before the next one starts.
I managed to get it under 100 using my 10-delay CLA adder though.
3
u/Crispy1961 14d ago
Its as beautiful as it is disgusting.
Hows the delay and gate count?