3 ms·
If you're building adders with O(n) carry times you're doing it wrong - normal carry lookahead logic is ~O(log N)
by Taniwha 6y ago
If you're building adders with O(n) carry times you're doing it wrong - normal carry lookahead logic is ~O(log N)
- gnramires 6y agoThe gate count for addition is at least O(n) though. You should note the O(log n) delay growth is for a logic (ideal) model. Considering the 2D geometry of real circuits, there are models with more detail, in particular VLSI models. [1] I suspect due to routing and path lengths even the delay would turn out to be O(n) in VLSI, or at least a power of n (with a small constant). [1] Seems like a good introduction: http://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation_Chapter12.pdf http://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputa...
- Taniwha 6y agoOh yeah definitely > O(n) - but we often trade gates (and area) for speed either by pipelining and/or more parallelism (which is what carry-lookahead logic is)