News for hackers. Stuff that matters.
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)
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...

Re:Memristor Breakthrough: First Single Device to Act Like a... by Taniwha on Friday October 02, 2020 @05:39AM (#24660763)
Oh 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)