Best way to carry on 2-input architecture?

Niels Möller nisse at
Wed Aug 20 20:02:26 UTC 2014

"Wesley W. Terpstra" <wesley at> writes:

>> But maybe you can do a circuit for mulhi which is significantly simpler
>> than for a widening multiplication, because you only need to collect the
>> carry out from the low partial products? Something like a Wallace tree
>> where you drop the low output bit from all the half and full adders of
>> the low product half.
> If you figure out a way to do this, please let me know.
> Personally, I don't see how this could be done. The Wallace tree can
> never reduce you to less than two rows. So, you still have to do the
> full adder to find the carry for the lower half.

Hmm. I'd have to work out a small example to see if I can make sense of

> Don't forget that ASICs do not use ripple adders. They use Kogge-Stone
> adders, or a variation with similar circuit depth,

Cool. This is way beyond what I was tought in the basic digital
electronics course at the university...

Original paper at,
but a bit too general for me to digest now. An easier description at

> So, for a 64x64 multiplier, the circuit starts with 1 level of 64x64
> AND gates, followed by 8 levels of 3:2 Wallace reduction, followed 6
> levels of a KS adder.

Ok, so it really is practical way to do an n=64 multiplier of this size
as a n^2 size combinatorial circuit, and then you split it into stages
at will if it turns out the propagation delay is larger than the clock


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list