Draft:Knuth–Eve algorithm

The Knuth-Eve algorithm is an algorithm for polynomial evaluation. Specifically, it can evaluate an arbitrary polynomial with real coefficients of one real variable. It preprocesses the coefficients of the polynomial to reduce the number of multiplications required at runtime.

The key ideas used in this algorithm were originally proposed by Donald Knuth. His procedure opportunistically exploits structure in the polynomial being evaluated Eve determined for which polynomials this structure exists, and they gave a simple method of preconditioning polynomials to endow them with that structure.

Algorithm

Preliminaries

Consider an arbitrary polynomial $p\in \mathbb {R} [x]$ of degree $n$. Assume that $n\geq 3$. Define $m$ such that: if $n$ is odd then $n=2m+1$, and if $n$ is even then $n=2m+2$.

Again, the goal is to create an algorithm that returns $p(x)$ given any $x\in \mathbb {R}$. The algorithm is allowed to depend on the polynomial $p$ itself. And ideally, it would use as few operations — as few additions and multiplications — as possible.

Overview

Using polynomial long division, we can write

$$p(x)=q(x)\cdot (x^{2}+\alpha )+(\beta x+\gamma ),$$

where, $x^{2}+\alpha$ is the divisor. Picking a value for $\alpha$ fixes both the quotient $q$ and the coefficients in the remainder $\beta$ and $\gamma$. Then, the key idea is to cleverly choose $\alpha$ such that $\beta =0$, so that

$$p(x)=q(x)\cdot (x^{2}+\alpha )+\gamma .$$

Finally, this procedure can be applied recursively to $q$, expressing

$$p(x)=\left(\left(q_{m}(x)\cdot (x^{2}+\alpha _{m})+\gamma _{m}\right)\cdots \right)\cdot (x^{2}+\alpha _{1})+\gamma _{1}.$$

After $m$ recursive calls, the quotient $q_{m}$ is either a linear or a quadratic polynomial. In that base case, it can be evaluated with (say) Horner's method.

References

• Muller, Jean-Michel (17 November 2016). Elementary functions: Algorithms and implementation. Boston, MA: Birkhäuser Boston. pp. 82–84. doi:10.1007/978-1-4899-7983-4_5. ISBN 978-1-4899-7983-4. Retrieved 25 July 2025.
• Overill, Richard (12 June 1997). "Data parallel evaluation of univariate polynomials by the Knuth-Eve algorithm". Parallel Computing. 23 (13): 2115–2127. doi:10.1016/S0167-8191(97)00096-3. Retrieved 25 July 2025.
• Mesztenyi, C. (January 1967). "Stable evaluation of polynomials". Journal of Research of the National Bureau of Standards - B. Mathematics and Mathematical Physics. 71B (1): 11–17. doi:10.6028/jres.071B.003. Retrieved 25 July 2025.
• Erickson, Jeff. "Evaluating polynomials" (PDF). CS 497: Concrete Models of Computation. University of Illinois Urbana-Champaign. Retrieved 25 July 2025.