I am fully braced for it to be a https://en.wikipedia.org/wiki/Galactic_algorithm
Very surprising result though! Multiplication is easier than sorting.
I am fully braced for it to be a https://en.wikipedia.org/wiki/Galactic_algorithm
Very surprising result though! Multiplication is easier than sorting.
Then 'n' means kind of different things for sorting vs. multiplication though. For example for sorting we assume constant time comparison, which doesn't make sense inputs of O(n) bits
If you sort n k-bit items for a total time of O(nk logn), that scales more poorly in n than multiplying n-word integers. Of course if k is constant you can do radix sort, but I genuinely don't know under what conditions radix sort is more/less galactic than this multiplication algorithm.
It would be absolutely unbelievable if such an improvement were practical.