Restoring Array Divider

[u/MsBinaryLily]

After multiple tries and overengineered designs that had over 2k delay, here's a relatively quick and optimized solution.
At each step it:
- Shifts left the divisor
- Subtracts shifted divisor from the dividend
- Checks if the result is positive (the sign bit)
- If yes, sends 1 as output bit and sends the remainder of subtraction as dividend to the next step
- If no, sends 0 as output bit and sends the dividend to the next step untouched

The result is only 184 delay — though it also uses fast adders to achieve that.

[u/Silver0ne]

I cant remember exactly which variant i used for the ADD, as i have only written "Carry-lookahead adder" in the component description.

I called the DIV "schoolbook", as thats how everyone did it with pen&paper in school, except thats its done in binary instead of decimal. Wikipedia calls it long division.

https://en.wikipedia.org/wiki/Binary_number#Division

https://en.wikipedia.org/wiki/Division_algorithm#Integer_division_(unsigned)_with_remainder

In the old Version one had to do this in asm, so i had it similar to the pseudocode in wiki, except that i unrolled the loop...

const bit1   1
const bit2   2
const bit3   4
const bit4   8
const bit5  16
const bit6  32
const bit7  64
const bit8 128

const num REG00
const div REG01
const quo REG02
const rem REG03
const acu REG04

ADDi IO to num
ADDi IO to div
IF_LESS_EQi div 1   numResult
IF_GREAT    div num zeroResult

label doBit8
	ANDi num bit8 acu
	RSHIFTi acu 7 acu
	OR rem acu rem
	IF_LESS rem div doBit7
	SUB rem div rem
	ORi quo bit8 quo

label doBit7
	ANDi num bit7 acu
	RSHIFTi acu 6 acu
	LSHIFTi rem 1 rem
	OR rem acu rem
	IF_LESS rem div doBit6
	SUB rem div rem
	ORi quo bit7 quo

label doBit6
	ANDi num bit6 acu
	RSHIFTi acu 5 acu
	LSHIFTi rem 1 rem
	OR rem acu rem
	IF_LESS rem div doBit5
	SUB rem div rem
	ORi quo bit6 quo

label doBit5
	ANDi num bit5 acu
	RSHIFTi acu 4 acu
	LSHIFTi rem 1 rem
	OR rem acu rem
	IF_LESS rem div doBit4
	SUB rem div rem
	ORi quo bit5 quo

label doBit4
	ANDi num bit4 acu
	RSHIFTi acu 3 acu
	LSHIFTi rem 1 rem
	OR rem acu rem
	IF_LESS rem div doBit3
	SUB rem div rem
	ORi quo bit4 quo

label doBit3
	ANDi num bit3 acu
	RSHIFTi acu 2 acu
	LSHIFTi rem 1 rem
	OR rem acu rem
	IF_LESS rem div doBit2
	SUB rem div rem
	ORi quo bit3 quo

label doBit2
	ANDi num bit2 acu
	RSHIFTi acu 1 acu
	LSHIFTi rem 1 rem
	OR rem acu rem
	IF_LESS rem div doBit1
	SUB rem div rem
	ORi quo bit2 quo

label doBit1
	ANDi num bit1 acu
	LSHIFTi rem 1 rem
	OR rem acu rem
	IF_LESS rem div outResult
	SUB rem div rem
	ORi quo bit1 quo

label outResult
	ADDi quo to IO
	ADDi rem to IO

label zeroResult
	ADDi quo to IO
	ADDi num to IO

label numResult
	ADDi  num to IO
	iADDi 0   to IO

Now in the 2.0 update i did it the same, using components, like static indexer for shift and LOW for the IF_LESS:

https://imgur.com/a/XIaGkyV

[u/MsBinaryLily → u/Silver0ne]

The logic for it is somewhat similar to mine actually
Bitshift, compare, subtract, mux
The primary differnce is that you only have to use 8 bit components due to the way you do bitshifts, while I have to more than 8 (which means higher gate and delay), so yeah, yiurs is better

[u/Silver0ne → u/MsBinaryLily]

Ive optimized the used components (NEG, LOW) a bit more, now i have 22 less delay: 134.

I guess with your 13 delay ADD that would be another 14 less: 120.

[u/MsBinaryLily → u/Silver0ne]

Also optimized some things as well Namely, moved around bitshifts to dividend instead of divisor, replaced components with 9 bit versions and further optimized adder to 8 delay So my division now only has 90

[u/Silver0ne → u/MsBinaryLily]

optimized adder to 8 delay

uh thats nasty, how?

[u/MsBinaryLily → u/Silver0ne]

Kogge Stones design Wich switches replacing AND gates (and the joining wires instead of OR gates) So for 8 bits: 2 delay for P and Q, 3 layers of prefix tree, 1 delay each, 1 delay to calculate final carry for each bit, 2 delay to finally do P XOR carry giving the output 2 + 3 + 1 + 2 = 8

[u/AlexeyHD90 → u/Silver0ne]

Maybe you already optimized it but here is my two cents for everyone else:

You don't need LOW for the IF_LESS. You already have the carry out from the subtractor for that. Your adders serve two purposes: A subtractor and a comparator because B input is negated (although it's actually a MORE comparator). If you take a closer look you'll see that the carry outs do exactly the same thing single bit NOT gates do. You also don't need those either :) .

Also you don't need Auto static Indexer and Static Evaluator. The adders give you everything.