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

This way, no operations are needed to compute the remainder polynomial, since it's just a constant. 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 at least $n-1$ roots of $p$ 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 most of 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$, sorted in descending order by real part
• Choose any $t\geq {\text{Re}}(r_{2})$
• 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 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$

Better choice of t

While any $t\geq {\text{Re}}(r_{2})$ can work, it is possible to remove one addition during evaluation if $t$ is also chosen such that two roots of $p(x+t)$ are symmetric about the origin. In that case, $\alpha _{1}$ can be chosen such that the shifted polynomial has a factor of $x^{2}-\alpha _{1}$, so $\gamma _{1}=0$.

It is always possible to find such a $t$. For example:

• If $r_{1}\in \mathbb {R}$:
  • If $r_{2}\in \mathbb {R}$: ${\textstyle t={\tfrac {1}{2}}(r_{1}+r_{2})}$
  • Else: $t={\text{Re}}(r_{2})$
• Else: $t={\text{Re}}(r_{1})$

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.

---

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

Assuming $t$ is chosen optimally, $\gamma _{1}=0$. So, the final iteration of the loop can instead run

$$y\gets y\cdot (s-\alpha _{i}),$$

saving an addition.

Analysis

In total, evaluation using the Knuth–Eve algorithm for a polynomial of degree $n$ requires $n$ additions and $\lfloor n/2\rfloor +2$ multiplications, assuming $t$ is chosen optimally.

No algorithm to evaluate a given polynomial of degree $n$ can use fewer than $n$ additions or fewer than $\lceil n/2\rceil$ multiplications during evaluation. This result assumes only addition and multiplication are allowed during both preprocessing and evaluation.

The Knuth–Eve algorithm is not well-conditioned.

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.