Re:How to multiply polynomials in Θ(n log n) time
by fdej on Monday September 07, 2015 @08:52PM
(#10183703)
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.
[ Parent
| on HN ]
Re:How to multiply polynomials in Θ(n log n) time
by ot on Tuesday September 08, 2015 @04:23AM
(#10184569)
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.