Interesting... what are the chances something like this gets implemented in Silicon and actually speeds up computation or is this purely of theoretical interest?
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!