3 ms·
> the standard adder designs have linear area in the number of bits, and logarithmic propagation time from inputs to outputs. It's a linear number of gates, bu
by a1369209993 4y ago
> the standard adder designs have linear area in the number of bits, and logarithmic propagation time from inputs to outputs.
It's a linear number of gates, but slightly worse than linear area due to routing. (I've looked for a strictly-linear design before, so if you have such a design, I'd quite appreciate a citation.) It's still much better than N log N area, though, so your point stands.
- atq2119 4y agoAdmittedly I hadn't considered routing. Do you have some reference, and how does it scale? Worse than linear but better than N log N is unusual...
- a1369209993 4y agoIf you lay out a carry-lookahead tree the naive way, it occupies a N x logN rectangle with the N-bit adder along the N side, but most of the rectangle is empty (each layer has half as many gates as the previous). You can easily pack it more densely on a ad hoc basis, but I don't know of a systematic approach, so possibly it's only a (mildly large) constant factor better than the naive way at scale. > Do you have some reference Nope; that's why I was asking for one.