Knuth–Eve algorithm: Difference between revisions

Revision as of 22:31, 30 July 2025

Revision as of 22:39, 30 July 2025

Line 9:

----

{{Short description|Algorithm for polynomialevaluating evaluationpolynomials}}

{{Draft topics|computing}}

{{AfC topic|stem}}

Line 15:

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

TheIn [[computer science]], the '''Knuth–Eve algorithm''' is an [[algorithm]] for [[polynomial evaluation]]. It [[Polynomial_evaluationPolynomial evaluation#Evaluation_with_preprocessingEvaluation with preprocessing|preprocesses]] the coefficients of the polynomial to reduce the number of multiplications required at [[Execution_Execution (computing)#Runtime|runtime]].

Ideas used in the algorithm were originally proposed by [[Donald Knuth]] in 1962. His procedure opportunistically exploits structure in the polynomial being evaluated.<ref name="knuth1962"/> 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.<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>}}

Line 25:

Consider an arbitrary polynomial <math>p \in \mathbb{R}[x]</math> of [[Degree of a polynomial|degree]] <math>n</math>. Assume that <math>n \geq 3</math>. Define <math>m</math> such that: if <math>n</math> is odd then <math>n = 2m+1</math>, and if <math>n</math> is even then <math>n = 2m+2</math>.{{cn|date=July 2025}}

Unless otherwise stated, all variables represent either [[Realreal number|real numbers]]s or univariate [[Polynomial|polynomialspolynomial]]s with real coefficients. All operations are done over <math>\mathbb{R}</math>.{{cn|date=July 2025}}

Again, the goal is to create an algorithm that returns <math>p(x)</math> given any <math>x</math>. The algorithm is allowed to depend on the polynomial <math>p</math> itself.{{cn|date=July 2025}}

Line 53:

<math display="block"> p(x) = p^e(x^2) + x \cdot p^o(x^2). </math>

If every [[Zero of a function#Polynomial roots|root]] of <math>p^o</math> is real, then it is possible to write <math>p</math> in the form given above. Each <math>\alpha_i</math> is a different root of <math>p^o</math>, counting [[Multiplicity (mathematics)#Multiplicity of a root of a polynomial|multiple roots]] as distinct.<ref name="overill1997"/> Furthermore, if at least <math>n-1</math> roots of <math>p</math> lie in one half of the [[Complex number|complex plane]], then every root of <math>p^o</math> is real.<ref name="eve1964"/>

Ultimately, it may be necessary to "precondition" <math>p</math> by shifting it {{--}} by setting <math>p(x) \gets p(x + t)</math> for some <math>t</math> {{--}} 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 <math>x \gets x - t</math>.{{cn|date=July 2025}}