|
| ▲ | kingstnap 4 hours ago | parent | next [-] |
| Yeah its ridiculously small, but any improvement on n log n is wild. Like there is somehow redundancy in a fourier transform that makes it sub Linearithmic? Which low and behold -> 130. Fourier transforms below n log n. |
| |
| ▲ | xyzzyz 4 hours ago | parent [-] | | They also separately give algorithm for Fourier transform over complex number faster than O(n log n) | | |
| ▲ | saalweachter 3 hours ago | parent [-] | | Wikipedia just told me there's a galactic algorithm for integer multiplication in O(n log n) based on FFT so I'm guessing those two proofs are related. |
|
|
|
| ▲ | sobellian 4 hours ago | parent | prev | next [-] |
| 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. |
| |
| ▲ | zeroonetwothree 3 hours ago | parent | next [-] | | 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 an hour ago | parent [-] | | 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. |
| |
| ▲ | senderista 3 hours ago | parent | prev [-] | | It would be absolutely unbelievable if such an improvement were practical. |
|
|
| ▲ | anon-3988 3 hours ago | parent | prev [-] |
| It fascinates me that there's something like this in something as solid and rigid like matrix multiplication. What causes something so rigid to break apart and "leak" at very large scale? Why does the "optimization" appear to be very, very small? Why does galactic algorithm exists? I can't imagine long division suddenly breaking apart after a billion digit, the structure seems very stable? I have heard before that matrix multiplication is apparently optimize-able at very, very large scale. Does anyone have an intuition to what causes it? What happens at these large scale (or very small)? |
| |
| ▲ | adgjlsfhk1 2 hours ago | parent [-] | | One way to think about it is that the classical algorithms are the ones that are fast for small numbers. Galactic algorithms often work for small inputs, it's just that to be faster you need big inputs. A common case of this is a requirement that log(n)<<klog(log(n)). If k=100 then this algorithm will take huge sizes to win |
|
