5 ms·
Interesting... what are the chances something like this gets implemented in Silicon and actually speeds up computation or is this purely of theoretical interest
by jgoodknight 8y ago
Interesting... what are the chances something like this gets implemented in Silicon and actually speeds up computation or is this purely of theoretical interest?
- deleted 8y ago[deleted]
- gaogao 8y agoIf the constants aren't too big, this might find use in signal processing.
- hackcasual 8y agoThe constants are massive. Like billions of digits.
- _0ffh 8y agoFor 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.
- wbhart 8y agoThe big-oh notation is an asymptotic notation, so it is meaningless to describe an imul as being O(n). Given that an imul is doing 64x64 bit multiplications, it is almost a tautology to say it can be done in a constant times 64 ops/cycles.
- _0ffh 8y agoThat was not what I was trying to say, wrong as I may still be. 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.
- lerax 8y ago> I think there are already time O(log n) multiplier circuits out there. This only can be magic! It's not possible!
- _0ffh 8y agoThere'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 https://en.wikipedia.org/wiki/Wallace_tree