Draft:Knuth–Eve algorithm

The Knuth-Eve algorithm is an algorithm for polynomial evaluation. 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$.

Unless otherwise stated, all variables represent either real numbers or univariate polynomials with real coefficients. All operations are done over $\mathbb {R}$.

Again, the goal is to create an algorithm that returns $p(x)$ given any $x$. The algorithm is allowed to depend on the polynomial $p$ itself.

Overview

Key idea

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$. The key idea is to cleverly choose $\alpha$ such that $\beta =0$, so that

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

We apply this procedure recursively to $q$, expressing

$$p(x)=\left(\left(q(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$ is either a linear or a quadratic polynomial. In this base case, the polynomial can be evaluated with (say) Horner's method.

"Preconditioning"

For arbitrary $p$, it may not be possible to force $\beta =0$ at every step of the recursion. Consider the polynomials $p^{e}$ and $p^{o}$ with coefficients taken from the even and odd terms of $p$ respectively, so that

$$p(x)=p^{e}(x^{2})+x\cdot p^{o}(x^{2}).$$

If every root of $p^{o}$ is real, then it is possible to write $p$ in the form given above. Each $\alpha _{i}$ is a different root of $p^{o}$, counting multiple roots as distinct. Furthermore, if all the roots of $p$ (except perhaps one) lie in one half of the complex plane, then every root of $p^{o}$ is real.

Ultimately, it may be necessary to "precondition" $p$ by shifting it — by setting $p(x)\gets p(x+t)$ for some $t$ — to endow it with the structure that all its roots lie in one half of the complex plane. At runtime, this shift has to be "undone" by first setting $x\gets x-t$.

Preprocessing step

The following algorithm is run once for a given polynomial $p$. Its results are used by the evaluation step, and they can be reused across many calls to that step.

At this point, the values of $x$ that $p$ will be evaluated on are not known.

• Let $r_{1},\cdots ,r_{n}\in \mathbb {C}$ be the complex roots of $p$
• Let ${\textstyle t=\max _{i=1}^{n}{\text{Re}}(r_{i})}$
• Set $p\gets p(x+t)$

---

• Let $p^{e}$ and $p^{o}$ be the polynomials such that $p(x)=p^{e}(x^{2})+x\cdot p^{o}(x^{2})$
• Let $\alpha _{1},\cdots \alpha _{m}\in \mathbb {R}$ be all the roots of $p^{o}$. All of its roots will be real.

---

• Initialize $q\gets p$
• For $i\gets 1,\cdots ,m$:
  • Divide $q$ by $x^{2}-\alpha _{i}$ to get quotient $q^{\prime }\in \mathbb {R} [x]$ and remainder $\gamma _{i}\in \mathbb {R}$. The remainder will be a constant polynomial — a number.
  • Set $q\gets q^{\prime }$

---

• Output: The derived values $t$, $\alpha _{1},\cdots ,\alpha _{m}$, and $\gamma _{1},\cdots ,\gamma _{m}$; as well as the base-case polynomial $q$

Evaluation step

The following algorithm evaluates $p$ at some, now known, point $x$. It consumes the output of the preprocessing step.

• Set $x\gets x-t$
• Let $s=x^{2}$. Compute this once so it can be reused throughout the algorithm.

---

• Compute $y\gets q(x)$ using Horner's method
• For $i\gets m,\cdots ,2,1$:
  • Let $y\gets y\cdot (s-\alpha _{i})+\gamma _{i}$
• Output: $y$

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.
• 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.