8 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 7y 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?
- gaogao 7y agoIf the constants aren't too big, this might find use in signal processing.
- hackcasual 7y agoThe constants are massive. Like billions of digits.
- deleted 7y ago[deleted]
- _0ffh 7y 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 7y 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 7y 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 7y ago> I think there are already time O(log n) multiplier circuits out there. This only can be magic! It's not possible!
- _0ffh 7y 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