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).
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)
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...