Fastest algorithm for evaluating large polynomials

Question

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.

Answer 1

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.