Knuth–Eve algorithm: Difference between revisions

Revision as of 06:50, 27 July 2025

Revision as of 06:52, 27 July 2025

Line 6:

<!-- Important, do not remove anything above this line before article has been created. -->

The '''Knuth-EveKnuth–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 ideas used in this algorithm were originally proposed by [[Donald Knuth]]. His procedure opportunistically exploits structure in the polynomial being evaluated.<ref name="knuth1962"/> Eve determined for which polynomials this structure exists, and they gave a simple method of [[#"Preconditioning"|"preconditioning"]] polynomials to endow them with that structure.<ref name="eve1964"/>

Line 111:

== Analysis ==

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

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

The Knuth-EveKnuth–Eve algorithm is not [[Condition number|well-conditioned]].<ref name="mesztenyi1967"/>

== Notes ==