3 ms·
You may know this, but the person you responded to almost certainly doesn't based on their question, so: Carry look-ahead adders are a thing. The number of log
by atq2119 4y ago
You may know this, but the person you responded to almost certainly doesn't based on their question, so:
Carry look-ahead adders are a thing. The number of logic levels for computing the highest carry bit is logarithmic in the width of the numbers being added, not linear. Doubling the width of the numbers does not cut your clock rate in half, though you do have to pay for the faster cycle time in added area (more logic gates). There are all sorts of different trade-offs that are possible in the constant terms, but the standard adder designs have linear area in the number of bits, and logarithmic propagation time from inputs to outputs.
- 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.