For actual silicon, this does not seem like a relevant result. I think there are already time O(log n) multiplier circuits out there.
Edit: A typical imul will probably be no more than O(n), just to add something less speculative.
Edit: A typical imul will probably be no more than O(n), just to add something less speculative.
I meant to talk about nxn bit multiplication. If you scale n then, given the same basic architecture, you will also scale the circuit delay. When the delay scales linearly with the number of bits, I'd call that architecture O(n) in time. To me that seems to make intuitive sense, even though I might have that wrong. The term imul I used merely as a short hand for integer multiplication. I was not alluding to any specific architecture or width, there are plenty of CPU architectures out there using that mnemonic.
This only can be magic! It's not possible!