Re:Memristor Breakthrough: First Single Device to Act Like a...
by Taniwha on Thursday October 01, 2020 @08:49PM
(#24657707)
If you're building adders with O(n) carry times you're doing it wrong - normal carry lookahead logic is ~O(log N)
[ Parent
| on HN ]
Re:Memristor Breakthrough: First Single Device to Act Like a...
by gnramires on Friday October 02, 2020 @05:17AM
(#24660665)
The 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/ModelsOfComputa...