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.^[1] Eve determined for which polynomials this structure exists, and they gave a simple method of "preconditioning" polynomials to endow them with that structure.^[2]

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

Unless otherwise specified, all variables represent real numbers.

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

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 }$ . Then, 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 .}$$ 

Finally, we apply this procedure recursively to ${\displaystyle q}$ , expressing

$${\displaystyle 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 ${\displaystyle m}$  recursive calls, the quotient ${\displaystyle q_{m}}$  is either a linear or a quadratic polynomial. In this base case, the polynomial can be evaluated with (say) Horner's method.^[1]

"Preconditioning"

For arbitrary ${\displaystyle p}$ , it may not be possible to force ${\displaystyle \beta =0}$  at every step of the recursion.^[1] Still, 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.^[3] Furthermore, if all the roots of ${\displaystyle p}$  (except perhaps one) 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 all 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}$ .

Preprocessing Steps

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

  ---

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

  ---

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

Runtime Steps

Notes

1. Knuth, Donald (December 1962). "Evaluation of polynomials by computer". Communications of the ACM. 5 (12): 595–599. doi:10.1145/355580.369074. Retrieved 25 July 2025.
2. Eve, J. (December 1964). "The evaluation of polynomials". Numerische Mathematik. 6 (1): 17–21. doi:10.1007/BF01386049. Retrieved 25 July 2025.
3. 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.

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.