Knuth–Eve algorithm

In computer science, 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.

Ideas used in the algorithm were originally proposed by Donald Knuth in 1962. His procedure opportunistically exploits structure in the polynomial being evaluated.^[1] In 1964, James Eve determined for which polynomials this structure exists, and gave a simple method of "preconditioning" polynomials (explained below) to endow them with that structure.^{[2][note 1]}

Algorithm

Preliminaries

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

Unless otherwise stated, all variables in this article represent either real numbers or univariate polynomials with real coefficients.^[1][2] All operations in this article are done over ${\displaystyle \mathbb {R} }$.^[2]

Again, the goal is to create an algorithm that returns ${\displaystyle p(x)}$ given any ${\displaystyle x}$. The algorithm is allowed to depend on the polynomial ${\displaystyle p}$ itself, since its coefficients are known in advance.^[1]

Overview

Key idea

Using polynomial long division, we can write

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

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

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

^[4] This way, no operations are needed to compute the remainder polynomial, since it's just a constant. We apply this procedure recursively to ${\displaystyle q}$, expressing

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

After ${\displaystyle m}$ recursive calls, the quotient ${\displaystyle q}$ is either a linear or a quadratic polynomial. In this base case, the polynomial can be evaluated with (say) Horner's method.^[1][4][5]

"Preconditioning"

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

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

If every root of ${\displaystyle p^{o}}$ is real, then it is possible to write ${\displaystyle p}$ in the form given above. Each ${\displaystyle \alpha _{i}}$ is a different root of ${\displaystyle p^{o}}$, counting multiple roots as distinct.^[4] Furthermore, if at least ${\displaystyle n-1}$ roots of ${\displaystyle p}$ lie in one half of the complex plane, then every root of ${\displaystyle p^{o}}$ is real.^[2]

Ultimately, it may be necessary to "precondition" ${\displaystyle p}$ by shifting it — by setting ${\displaystyle p(x)\gets p(x+t)}$ for some ${\displaystyle 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 ${\displaystyle x\gets x-t}$.^[2]

Preprocessing step

The following algorithm is run once for a given polynomial ${\displaystyle p}$.^[1][4] At this point, the values of ${\displaystyle x}$ that ${\displaystyle p}$ will be evaluated on are not known.^[1]

• Let ${\displaystyle r_{1},\cdots ,r_{n}\in \mathbb {C} }$ be the complex roots of ${\displaystyle p}$, sorted in descending order by real part
• Choose any ${\displaystyle t\geq {\text{Re}}(r_{2})}$
• Set ${\displaystyle p\gets p(x+t)}$

---

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

---

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

---

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

Better choice of t

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

One possible algorithm for choosing ${\displaystyle t}$ is:^{[citation needed]}

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

Evaluation step

The following algorithm evaluates ${\displaystyle p}$ at some, now known, point ${\displaystyle x}$.^[1][2][4][5]

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

---

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

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

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

saving an addition.^[2]

Analysis

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

No algorithm to evaluate a given polynomial of degree ${\displaystyle n}$ can use fewer than ${\displaystyle n}$ additions or fewer than ${\displaystyle \lceil n/2\rceil }$ multiplications during evaluation. This result assumes only addition and multiplication are allowed during both preprocessing and evaluation.^{[6][better source needed]}

The Knuth–Eve algorithm is not well-conditioned.^[7]

Footnotes

1. Article published under the name J. Eve, which is associated with the name James Eve by the ACM Digital Library.^[3]