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

There are no comments on this comment yet.