Knuth–Eve algorithm: Difference between revisions

Revision as of 18:52, 31 July 2025

Latest revision as of 10:05, 22 August 2025

(5 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Algorithm for evaluating polynomials}}

{{Draft topics|computing}}

{{AfC topic|stem}}

{{AfC submission|||ts=20250731005752|u=Ammrat13|ns=118}}

{{AFC submission|d|reason|Awaiting additional information. Please address the cn tags.|u=Ammrat13|ns=118|decliner=Caleb Stanford|declinets=20250730220006|ts=20250727062925}} <!-- Do not remove this line! -->

{{AFC comment|1=Please disregard previous question, see [[Draft talk:Knuth–Eve algorithm|talk page discussion]] instead. Once this and the cn tags are addressed we can resubmit. Thanks! [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 22:25, 30 July 2025 (UTC)}}

{{AFC comment|1={{Question}} Where did you find that the author is James? It's [https://link.springer.com/article/10.1007/BF01386049 not in the source article] which you linked. [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 21:57, 30 July 2025 (UTC)}}

{{AFC comment|1=Likely notable, but do we know who "J. Eve" is? It isn't mentioned in the lead or body, and it should be covered. Please also add more inline citations to all uncited content. There are no citations in the "Preprocessing step" section for example. [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 16:21, 29 July 2025 (UTC)}}

----

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

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]].

Line 85 ⟶ 69:

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"/>

One possible algorithm for choosing <math>t</math> is:{{cn|date=July 2025}}

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

Line 95 ⟶ 79:

{{frame-footer}}

</div>

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

=== Evaluation step ===

Line 123 ⟶ 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"/>

Line 135 ⟶ 118:

{{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=James |title=The evaluation of polynomials |journal=Numerische Mathematik |date=December 1964 |volume=6 |issue=1 |pages=17–21 |doi=10.1007/BF01386049 |url=https://link.springer.com/article/10.1007/BF01386049 |access-date=25 July 2025|url-access=subscription }}</ref>

<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=Charles |title=Stable evaluation of polynomials |journal=Journal of Research of the National Bureau of Standards - B. Mathematics and Mathematical Physics |date=January 1967 |volume=71B |issue=1 |pages=11–17 |doi=10.6028/jres.071B.003 |url=https://nistdigitalarchives.contentdm.oclc.org/digital/collection/p16009coll6/id/87671 |access-date=25 July 2025}}</ref>

<ref name="muller2016">{{cite book |last1=Muller |first1=Jean-Michel |title=Elementary functions: Algorithms and implementation |date=17 November 2016 |publisher=Birkh&auml;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}}</ref>

}}

{{DEFAULTSORT:Knuth-Eve algorithm}}

[[Category:Algorithms]]

[[Category:Polynomials]]

[[Category:Algorithms and data structures]]