5 ms·
Are you sure you're using this algorithm [1] in your daily work and not a different one? It's the only known O(n log n) multiplication algorithm AFAIK. And if
by dataflow 5y ago
Are you sure you're using this algorithm [1] in your daily work and not a different one? It's the only known O(n log n) multiplication algorithm AFAIK.
And if so, can I ask what it's useful for? I thought it was a galactic algorithm.
[1] https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document
- enriquto 5y agoNo, I don't multiply integers, but polynomials, where the standard "fast" algorithm is nlogn
- dataflow 5y agoOh. I think the comment you replied to was talking about integer multiplication, not polynomial.
- adgjlsfhk1 5y agoto be specific, this is nlogn arithmetic operations, which isn't nlogn if you are doing exact math.
- enriquto 5y agosure, my coefficients are just floating-point numbers. I work in signal processing and when the OP said "multiplication" I could only think about applying a linear filter to a signal.
- adgjlsfhk1 5y agoIt's unknown whether it is a galactic algorithm (with some minor tweaks). According to the author, the version they published is optimized for simplicity and paper length rather than speed, but he thinks a lot of the constants can be made much lower. It's still quite likely galactic, but with some tweaks, it might not be. Also, in practice, I think their first algorithm that is nlogn subject to unproven (but likely) conjectures about the distribution of primes is more likely to be good computationally, but I am way out of my depth here.