3 ms·

This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algor

This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algorithm (just throw in some carries at the end), but O(n lg n) multiplication is an open problem. In this case the issue is that you need more and more precision for the FFT as the inputs get larger, or else you'll get the wrong answer. I think it ends up being an O(n log^2 n) algorithm. Still pretty good; worth knowing about for sure. The constant factor on the precision might be bad enough that you can trigger the problem for reasonable inputs if you're using floats (e.g. a million coefficients, instead of an octillion coefficients). On the other hand, many algorithms and data structures have hidden logarithmic factors (e.g. hash tables, sorting) that we ignore [1]. YMMV. 1: http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html http://blog.computationalcomplexity.org/2009/05/shaving-logs...

pbsd 11y ago
The best complexity these days [1] is essentially n log n. More precisely, O( n log n 8^(log* n) ), where log* is the extremely slow-growing iterated logarithm. The original Schönhage-Strassen algorithm is O(n log n log log n). [1] http://arxiv.org/abs/1407.3360 http://arxiv.org/abs/1407.3360
ot 11y ago
IIRC if your polynomials have integer coefficients with a bounded number of digits you can use FFT on finite rings and get an actual O(n log n) algorithm.
- fdej 11y ago
  This is not quite correct. A finite ring can only have finitely many primitive roots of unity, so the length of the FFTs you can compute in a ring of fixed size is bounded. To compute arbitrarily long convolutions over a finite ring, you need to extend the ring with more roots of unity (for example, using the Schönhage-Strassen trick), and this increases the complexity.
  - ot 11y ago
    I think you're right, but it depends on what's your computational model. In word-RAM you usually assume that log n < w where w is the machine word, and you can do arithmetical operations on words in O(1), so if your coefficients fit in w bits the complexity is O(n log n). You could say it's a trick but it's a convenient trick, since on a real-world machines w is much larger than you need (64). I don't know if you can make the same argument about floating point computations.
- Strilanc 11y ago
  The number of digits needed to hold an output coefficient (and intermediate coefficients during the transform) increases with the number of input coefficients (because so many get added together). This forces the size of the ring to increase to accommodate the larger values, and pushes the runtime past O(n lg n).
abetusk 11y ago
Chapter 1 [1] of Chee Yap's "Fundamental Problems of Algorithmic Algebra" [2] gives integer multiplication at O(n lg(n) lg(lg(n))). To prove that bound a "discrete Fourier transform" is used using modular arithmetic over 2^L + 1 (for suitable L). As you say, you can always convert to an integer multiplication problem so it stands at O(n lg(n) lg(lg(n))) (not O(n lg^2(n))). [1] http://cs.nyu.edu/~yap/book/alge/ftpSite/l1.ps.gz http://cs.nyu.edu/~yap/book/alge/ftpSite/l1.ps.gz [2] https://www.cs.nyu.edu/yap/book/berlin/ https://www.cs.nyu.edu/yap/book/berlin/

pbsd 11y ago

The best complexity these days [1] is essentially n log n. More precisely, O( n log n 8^(log* n) ), where log* is the extremely slow-growing iterated logarithm. The original Schönhage-Strassen algorithm is O(n log n log log n). [1] http://arxiv.org/abs/1407.3360 http://arxiv.org/abs/1407.3360

ot 11y ago

IIRC if your polynomials have integer coefficients with a bounded number of digits you can use FFT on finite rings and get an actual O(n log n) algorithm.

fdej 11y ago
This is not quite correct. A finite ring can only have finitely many primitive roots of unity, so the length of the FFTs you can compute in a ring of fixed size is bounded. To compute arbitrarily long convolutions over a finite ring, you need to extend the ring with more roots of unity (for example, using the Schönhage-Strassen trick), and this increases the complexity.
- ot 11y ago
  I think you're right, but it depends on what's your computational model. In word-RAM you usually assume that log n < w where w is the machine word, and you can do arithmetical operations on words in O(1), so if your coefficients fit in w bits the complexity is O(n log n). You could say it's a trick but it's a convenient trick, since on a real-world machines w is much larger than you need (64). I don't know if you can make the same argument about floating point computations.
Strilanc 11y ago
The number of digits needed to hold an output coefficient (and intermediate coefficients during the transform) increases with the number of input coefficients (because so many get added together). This forces the size of the ring to increase to accommodate the larger values, and pushes the runtime past O(n lg n).

abetusk 11y ago

Chapter 1 [1] of Chee Yap's "Fundamental Problems of Algorithmic Algebra" [2] gives integer multiplication at O(n lg(n) lg(lg(n))). To prove that bound a "discrete Fourier transform" is used using modular arithmetic over 2^L + 1 (for suitable L). As you say, you can always convert to an integer multiplication problem so it stands at O(n lg(n) lg(lg(n))) (not O(n lg^2(n))). [1] http://cs.nyu.edu/~yap/book/alge/ftpSite/l1.ps.gz http://cs.nyu.edu/~yap/book/alge/ftpSite/l1.ps.gz [2] https://www.cs.nyu.edu/yap/book/berlin/ https://www.cs.nyu.edu/yap/book/berlin/