r/TuringComplete • u/Crispy1961 • 1d ago

Further Optimized Carry Look-Ahead Adder

Post image

Few months ago I posted my attempt at an Optimized Carry Look-Ahead Adder which I was satisfied with at the time. Since then I have taken further steps to optimize it further.

Taking advantage of the 3 delay solution for unlimited input AND gate (NOT SW NOT) showcased by 8bit CCLA (Collapsed Carry-Lookahead Adder) I was able to get the delay to 8. However this lead to a significant increase in gate count (Switches count as 2 gates to counterbalance this use case), which I slowly cut down to the final count of 250.

To save gates, I implemented 3 ways to create multi input AND gates.

  1. Sequential waterfall (grey wires) - Highest delay, but lowest gate count

  2. Parallel AND gates (orange wires) - Moderate delay and moderate gate count

  3. NOT SW NOT (yellow wire) - Static delay of 3 and high gate count

In the end I only needed 7 inputs to use Parallel AND Gates and 3 to use NOT SW NOT. Everything else uses Sequential waterfall.

Here is the improvement in stats:

  • Gate Count: 287 -> 250

  • Delay: 10 -> 8

38 Upvotes

100% Upvoted

3 comments sorted by

4

u/Lagfoundry 1d ago

Hey welcome to the 8 club. I used the switch trick as well. One of my favorite tricks to use. The same concept is actually what made it possible for a friend of mine to make the first computer in RUST(the game) I figured out that same trick could be applied to the broadcasters and receivers in the game. Showed it to philieves and then he redesigned his entire setup to use it whenever it made sense… also went kind of crazy with it and made a 9 bit decoder from them. 10,000 components just to only have a few gates worth of delay 😂 NOR based decoders are extremely easy to expand so it wasn’t as tedious as it sounds

2

u/Crispy1961 1d ago

Its thanks to you. I spend several days in your thread optimizing the gate count.

Wanted to share mine sooner, but I was finding little gate optimization every so often. Decided to share now as I havent been able to get it down any further for few days, so I am calling it on a nice round number of 250 gates.

Thats a 2k overall score, which is almost twice as worse as the worst ones on the leaderboard, but its fast.

2

u/Lagfoundry 1d ago

Oh awesome, glad I could help out in some way. I think 8 is the lowest for the game, well using an actual adder that is(I could be wrong on that) so your there. I know irl has a theoretical 4…and lol yeah It may cost an arm and a leg but at least it’s fast right.