3 ms·
Even if n*log(n) turns out to be asymptotically "perfect", I'm curious what the constant overhead is. If it takes 15 minutes to multiply two 64-bit numbers, it
by notfed 8y ago
Even if n*log(n) turns out to be asymptotically "perfect", I'm curious what the constant overhead is.
If it takes 15 minutes to multiply two 64-bit numbers, it might not be as "perfect".
- colatkinson 8y agoFrom this article written by the author [0], the overhead is very high. So I don't think you'll be seeing this implemented in your CPU any time soon. The usefulness seems to be that (1) it's a cool new piece of theory and (2) it's significant if you're doing computational work on ridiculously large numbers, like massive primes or something. Gaps between theoretically optimal and practically optimal algorithms are extremely common. [0]: https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923 https://theconversation.com/weve-found-a-quicker-way-to-mult...