4 ms·
Adding on to this, and related somewhat, binary addition even with look ahead is a multi clock cycle process for non trivial word sizes. Arithmetic is not trivi
by marktangotango 3y ago
Adding on to this, and related somewhat, binary addition even with look ahead is a multi clock cycle process for non trivial word sizes. Arithmetic is not trivial by any means. We all just take it for granted.
- taeric 3y agoBy "non-trivial word sizes," I presume you mean larger than a single word of most computers? My understanding is that modern BDD/ZDD techniques have gone a long way to showing how to do the entire operation in a single pass for most sized numbers. Such that propagating the carry information isn't really how it is done, anymore. (This is a genuine question, btw. I have been a long way from my VLSI classes back in college.)
- throwaway14356 3y agomy ignorant imagination says to look for the sweetspot between a lookup table and chunks as large as possible.
- pfdietz 3y agoAddition can be performed with circuits of depth O(log n), where n is the number of bits, and with a little more work also of size O(n).
- ithkuil 3y agoI'm confused. Since O(log n) is faster than O(n) why would O(n) require a little more work? Did I misread something or did you miswrite?
- pfdietz 3y agoI'm talking about constructing boolean circuits. The usual parallel prefix algorithm yields a circuit of depth O(log n) with O(n log n) gates. Using some trickery, however, this can be reduced to O(n) gates, with a constant factor increase in depth. https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Adder_(electronics) https://en.wikipedia.org/wiki/Adder_(electronics)