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

There are no comments on this comment yet.