Comment by sobellian

1 day ago

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.

6 comments

sobellian

Reply
zeroonetwothree  1 day ago

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

  • sobellian  21 hours ago

    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.

    • adgjlsfhk1  19 hours ago

      this alg is way more galactic than radix sort. radix sort often wins in the hundreds of elements. the nlogn multiplication requires numbers with more digits than atoms in the universe (although that could probably be brought down a lot)

      2 replies →