4 ms·
This was improved to O(n·logn·loglogn)[0], and very recently has been improved still further to O(n·logn)[1] - discussed here[2]. O(n·logn) has for some time b
by ColinWright 7y ago
This was improved to O(n·logn·loglogn)[0], and very recently has been improved still further to O(n·logn)[1] - discussed here[2].
O(n·logn) has for some time been conjectured to be the lower bound.
[0] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
[1] https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document
[2] https://news.ycombinator.com/item?id=19474280 https://news.ycombinator.com/item?id=19474280
- excessive 7y agoIf it could go lower than n log n, that would have huge implications for signal processing. Multiplication, convolution, and FFTs are all so similar to each other.
- dreamcompiler 7y agoKaratsuba is still quite useful for medium-length numbers that are too short for the faster methods to be worthwhile.
- fny 7y agoI always thought the Russian peasants algorithm was faster than this at O(log n). Can someone explain what I've misunderstood?
- naniwaduni 7y agoConventionally n is the length of the input, which is generally logarithmic in the numerical value of the input for algorithms dealing in integers. Moreover, analyzing Russian peasant multiplication as O(log N) implies treating addition as constant-time, which it certainly isn't. (This is intuitively clear if we try applying the algorithm with slightly large integers!)
- olliej 7y agoThe O(NlogN) algorithms all have very large constant factors - IIRC the crossover point from karatsuba or tooms to FFT based solutions (the NlogN algorithms) is in the thousands of digits.
- jacobolus 7y agoThe recent O(n log n) algorithm is only useful for numbers of size larger than 2^(2^(9^12)). Which is to say, this will never be of practical use in our universe. (Of course, conceivably someone else could invent a different algorithm of the same asymptotic complexity with a more reasonable constant factor.) But it’s still nice to have a proof that this lower bound is attainable in theory. Makes it easier to write down the theoretical lower bound for a wide variety of other algorithms.