[Libre-soc-bugs] [Bug 238] POWER Compressed Formal Standard writeup

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=238

--- Comment #138 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Alexandre Oliva from comment #137)
> what that arrangement does is to avoid having to work out the dependencies
> in full, and avoid cascading dependencies.  it trades working out and
> optimizing the actual dependencies, possibly simplified by O(n) cascading,
> for O(2^n) parallel-precomputing gates, followed by O(log n) selection and
> aggregation.

Please read the code again, you will find that the total gate count is O(N + N
* log N) == O(N * log N), with O(log N) circuit depth.

-- 
You are receiving this mail because:
You are on the CC list for the bug.