Knuth–Eve algorithm: Difference between revisions

Revision as of 23:43, 29 July 2025

Revision as of 23:47, 29 July 2025

Line 94:

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

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

Line 122:

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

== NotesReferences ==

{{reflist |refs=

Line 130:

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

}}

== References ==

{{refbegin}}

* {{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}}

{{refend}}