Content deleted Content added
Submitting using AfC-submit-wizard |
Citation bot (talk | contribs) Add: doi-broken-date, doi. | Use this bot. Report bugs. | Suggested by Eastmain | #UCB_webform 88/234 |
||
Line 19:
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) |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>}}
== Algorithm ==
| |||