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.
[ Parent
| on HN ]
There are no comments on this comment yet.