Hey everyone.
A rather general question, what is the fastest (in terms of time complexity) algorithm for evaluating polynomials of Degree 400 to 500.
Thanks in advance.
A:
Modified versions of fast Fourier transforms (FFTs) generally provide very good results for this sort of problem. Take a look at this paper, which suggests taking a hybrid FFT approach. I would start your research by looking for terms along the lines of "fast univariate FFT". It may also help you to note that multiplying two polynomials is essentially the same operation as multiplying two integers.
John Feminella
2009-12-09 21:09:14
+5
A:
If you are talking about evaluation of polynomials, you probably can't be faster than the linear time Horner scheme - except if you have some special circumstances.
If you are talking about the multiplication of polynomials, the Karatsuba algorithm is rather easy to implement and quite fast for that size. I believe fast Fourier transform based algorithms are only worth using if you have larger polynomials.
hstoerr
2009-12-09 21:20:53
+1 for Horner...much better than my first glance (as always).
Jason Punyon
2009-12-09 21:33:44
Horner is not only fast, but resistant to some instances of loss of precision erros that can plague really naive approaches.
dmckee
2009-12-09 22:02:04