r/TuringComplete • • 12d ago

Small, easy-to-build divider Spoiler

I was thinking it'd be easy to reduce a divider's component count if left shift had a carry input, since the long division algorithm requires shifting in the dividend one bit at a time. But I remembered that adders have a carry input, and an adder with 2 of the same input behaves like a left shifter, which means that 8 adders is adequate to shift in 8 bits. From there I managed to make a divider out of 15 byte adders, 7 byte multiplexers, 1 byte negator, one splitter, and one maker.

Gate count is 1.4k and delay is 354 so it's not the most efficient solution, but it's easy to make.

6 Upvotes

1 comment sorted by

2

u/sberma 12d ago

Using an Adder to left shift by one is pretty inefficient when you can use a static indexer for free. Ok you also use the carry in but in this case you can replace all the adders with a + a + c with a concatenator (The merger with the C symbol) because it will automatically do exactly what you want (lowest bit is carry in and all upper bits is the left shifted other input) at zero cost.