Content deleted Content added
Add more citations |
m v2.05 - Fix errors for CW project (DEFAULTSORT missing for titles with special letters) |
||
| (24 intermediate revisions by 5 users not shown) | |||
Line 1:
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) |url=https://dl.acm.org/do/10.1145/contrib-81100250587/abs/ |access-date=2025-07-30 |website=Author DO Series | publisher=ACM Digital Library |doi=10.1145/contrib-81100250587/abs |doi-broken-date=31 July 2025 |language=en}}</ref>}}
▲{{Short description|Algorithm for polynomial evaluation}}
▲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]].
== Algorithm ==
Line 19 ⟶ 9:
=== 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>.<ref name="eve1964"/>
Unless otherwise stated, all variables in this article represent either [[
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, since its coefficients are known in advance.<ref name="knuth1962"/>
=== Overview ===
Line 37 ⟶ 27:
<math display="block"> p(x) = q(x) \cdot (x^2 - \alpha) + \gamma. </math>
<ref 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
<math display="block"> p(x) = \left( \left( q(x) \cdot (x^2 - \alpha_m) + \gamma_m \right) \cdots \right) \cdot (x^2 - \alpha_1) + \gamma_1. </math>
After <math>m</math> recursive calls, the quotient <math>q</math> is either a [[Linear function (calculus)|linear]] or a [[Quadratic function|quadratic]] polynomial. In this base case, the polynomial can be evaluated with (say) [[Horner's method]].<ref name="knuth1962"/><ref name="overill1997"/><ref name="muller2016"/>
==== "Preconditioning" ====
Line 49 ⟶ 39:
<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 [[
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>.<ref name="eve1964"/>
=== Preprocessing step ===
The following algorithm is run once for a given polynomial <math>p</math>.<ref name="knuth1962"/><ref name="overill1997"/>
<div style="margin-left: 35px;">
Line 79 ⟶ 67:
==== 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"/>
<div style="margin-left: 35px;">
Line 94 ⟶ 82:
=== 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
<div style="margin-left: 35px;">
Line 118 ⟶ 106:
In total, evaluation using the Knuth–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.<ref name="eve1964"/>
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"/>{{Better source needed|date=July 2025}}
The Knuth–Eve algorithm is not [[Condition number|well-conditioned]].<ref name="mesztenyi1967"/>
==
{{Reflist|group=note}}
== References ==▼
{{reflist |refs=
<ref name="knuth1962">{{cite journal |last1=Knuth |first1=Donald |title=Evaluation of polynomials by computer |journal=Communications of the ACM |date=December 1962 |volume=5 |issue=12 |pages=595–599 |doi=10.1145/355580.369074 |url=https://dl.acm.org/doi/10.1145/355580.369074 |access-date=25 July 2025}}</ref>
<ref name="eve1964">{{cite journal |last1=Eve |first1=
<ref name="overill1997">{{cite journal |last1=Overill |first1=Richard |title=Data parallel evaluation of univariate polynomials by the Knuth-Eve algorithm |journal=Parallel Computing |date=12 June 1997 |volume=23 |issue=13 |pages=2115–2127 |doi=10.1016/S0167-8191(97)00096-3 |url=https://www.sciencedirect.com/science/article/pii/S0167819197000963 |access-date=25 July 2025|url-access=subscription }}</ref>
<ref name="erickson2003">{{cite web |last1=Erickson |first1=Jeff |title=Evaluating polynomials |date=10 March 2003 |url=https://jeffe.cs.illinois.edu/teaching/497/08-polynomials.pdf |website=CS 497: Concrete Models of Computation |publisher=University of Illinois Urbana-Champaign |access-date=25 July 2025}}</ref>
<ref name="mesztenyi1967">{{cite journal |last1=Mesztenyi |first1=
}}
{{DEFAULTSORT:Knuth-Eve algorithm}}
▲== References ==
[[Category:Algorithms]]
[[Category:Polynomials]]
▲* {{cite book |last1=Muller |first1=Jean-Michel |title=Elementary functions: Algorithms and implementation |date=17 November 2016 |publisher=Birkhäuser Boston |___location=Boston, MA |isbn=978-1-4899-7983-4 |doi=10.1007/978-1-4899-7983-4_5 |pages=82–84 |url=https://link.springer.com/chapter/10.1007/978-1-4899-7983-4_5 |access-date=25 July 2025}}
[[Category:Algorithms and data structures]]
| |||