Fast Evaluation of Polynomials with Rational Preprocessing

Thomas D. Ahle, Jakob B. T. Knudsen

Horner's rule evaluates a monic degree-$n$ polynomial using $n-1$ multiplications. We show that with rational preprocessing of the coefficients, any such polynomial can be evaluate…