Hacker News new | ask | show | jobs
by lerax 2642 days ago
> I think there are already time O(log n) multiplier circuits out there.

This only can be magic! It's not possible!
1 comments
_0ffh 2642 days ago
There's always a time/space tradeoff involved, see for example the Wallace tree multiplier [1], which is indeed O(log n) in time.

[1] https://en.wikipedia.org/wiki/Wallace_tree

link