Fastest algorithm for evaluating large polynomials

A rather general q开发者_开发问答uestion, what is the fastest (in terms of time complexity) algorithm for evaluating polynomials of Degree 400 to 500.

Thanks in advance.

---

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.

---

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.