Knuth–Eve algorithm: Difference between revisions

Revision as of 22:39, 30 July 2025

Revision as of 00:34, 31 July 2025

Line 17:

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

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 | publisher=ACM Digital Library |language=en}}</ref>}}

== Algorithm ==

Line 23:

=== Preliminaries ===

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<ref 2025}}name="eve1964"/>

Unless otherwise stated, all variables in this article represent either [[real number]]s or univariate [[polynomial]]s with real coefficients. All operations in this article are done over <math>\mathbb{R}</math>.{{cn|date<ref name=July 2025}}"eve1964"/>

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<ref 2025}}name="knuth1962"/>

=== Overview ===

Line 39:

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

<math display="block"> p(x) = q(x) \cdot (x^2 - \alpha) + \gamma. </math>{{cn|date<ref name=July"knuth1962"/><ref 2025}}name="overill1997"/>

This way, no operations are needed to compute the remainder polynomial, since it's just a constant. We apply this procedure [[Recursion (computer science)|recursively]] to <math>q</math>, expressing

Line 55:

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 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<ref 2025}}name="eve1964"/>

=== Preprocessing step ===

The following algorithm is run once for a given polynomial <math>p</math>.<ref name="knuth1962"/><ref name="overill1997"/> ItsAt resultsthis are used bypoint, the [[#Evaluationvalues step|evaluationof step]],<math>x</math> andthat they<math>p</math> canwill be reusedevaluated acrosson manyare callsnot toknown.<ref that step.name="knuth1962"/>

At this point, the values of <math>x</math> that <math>p</math> will be evaluated on are not known.{{cn|date=July 2025}}

<div style="margin-left: 35px;">

Line 83 ⟶ 81:

==== Better choice of t ====

While any <math>t \geq \text{Re}(r_2)</math> can work, it is possible to remove one addition during evaluation if <math>t</math> is also chosen such that two roots of <math>p(x + t)</math> are symmetric about the origin. In that case, <math>\alpha_1</math> can be chosen such that the shifted polynomial has a factor of <math>x^2 - \alpha_1</math>, so <math>\gamma_1 = 0</math>. It is always possible to find such a <math>t</math>.<ref name="eve1964"/>

It is alwaysOne possible toalgorithm findfor such achoosing <math>t</math>.{{cn|date=July 2025}} For exampleis:

<div style="margin-left: 35px;">

Line 95 ⟶ 93:

{{frame-footer}}

</div>

{{cn|date=2025-07-31}}

=== Evaluation step ===

The following algorithm evaluates <math>p</math> at some, now known, point <math>x</math>.<ref name="knuth1962"/><ref name="eve1964"/><ref name="overill1997"/><ref name="muller2016"/> It consumes the output of the [[#Preprocessing step|preprocessing step]].{{cn|date=July 2025}}

<div style="margin-left: 35px;">