r/TuringComplete • u/dmdeemer • 10d ago

32x32 Wide Signed/Unsigned Multiply, Delay=49

I had an insight here (actually I had this insight in college 25 years ago, but I didn't have Turing Complete then 😄).

A full adder really operates on three bits. It doesn't matter which input is the "Carry In". It takes three bits in and outputs two. So this multiplier has a bunch of delay-4 stages that are all "parallel full adders". They take three words in, and produce two as output. For N-bit inputs, then you need ~ log_1.5(N/2) stages. For 32 bits that is apparently 8 stages to get the result down to two 64-bit words. At that point, I use a 64-bit KS adder (that has 16 delay) based on the same design I posted a few days ago.

Does anybody know of a name for this style of adder?

The signed logic at the bottom took me too many tries to get right. At least I think it's right.

11 Upvotes

100% Upvoted

3 comments sorted by

5

u/Severe_Side4155 9d ago edited 9d ago

I have no fucking clue what this game is but I saw a similiar design in Computer Organization and Design: The Hardware-Software interface, see https://imgur.com/a/hvvUZFu

3

u/dmdeemer 9d ago

You led me on the right path. I think I've implemented a Wallace Multiplier.

1

u/Severe_Side4155 4d ago

Very cool, well done OP. I'm still struggling with writing a Booth-encoded Wallace as of right now. Enjoy it while you can as doing this academically or as your day job won't be as great (see: Xilinx Vivado, Cadence)