News for hackers. Stuff that matters.
Re:How to multiply polynomials in Θ(n log n) time by abetusk on Monday September 07, 2015 @11:34PM (#10184024)
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

[2] https://www.cs.nyu.edu/yap/book/berlin/

There are no comments on this comment yet.