The '''Knuth–Eve algorithm''' is an [[algorithm]] for [[polynomial evaluation]]. It [[Polynomial_evaluation#Evaluation_with_preprocessing|preprocesses]] the coefficients of the polynomial to reduce the number of multiplications required at [[Execution_(computing)#Runtime|runtime]].
The key ideasIdeas used in thisthe algorithm were originally proposed by [[Donald Knuth]] in 1962. His procedure opportunistically exploits structure in the polynomial being evaluated.<ref name="knuth1962"/> [[JamesIn Eve1964, (computer scientist)|James Eve]] determined for which polynomials this structure exists, and they gave a simple method of [[#"Preconditioning"|"preconditioning"]] polynomials (explained below) to endow them with that structure.<ref name="eve1964"/>{{refn|group=note|Article published under the name J. Eve, which is associated with the name James Eve by the ACM Digital Library.<ref name=JamesEveACMDL>{{Cite web |title=James Eve (Newcastle University) - ACM Digital Library |url=https://dl.acm.org/do/10.1145/contrib-81100250587/abs/ |access-date=2025-07-30 |website=Author DO Series |language=en}}</ref>}}
== Algorithm ==
Line 125:
The Knuth–Eve algorithm is not [[Condition number|well-conditioned]].<ref name="mesztenyi1967"/>
