Draft:Knuth–Eve algorithm
 | Draft article not currently submitted for review.
This is a draft Articles for creation (AfC) submission. It is not currently pending review. While there are no deadlines, abandoned drafts may be deleted after six months. To edit the draft click on the "Edit" tab at the top of the window. To be accepted, a draft should:
It is strongly discouraged to write about yourself, your business or employer. If you do so, you must declare it. Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
Last edited by Ammrat13 (talk | contribs) 4 days ago. (Update) |
The Knuth-Eve Algorithm is an algorithm for polynomial evaluation. Specifically, it can evaluate an arbitrary polynomial with real coefficients of one real variable. It preprocesses the coefficients of the polynomial to reduce the number of multiplications required at runtime.
The key ideas used in this algorithm were originally proposed by Donald Knuth. His procedure opportunistically exploits structure in the polynomial being evaluated[1] J. Eve determined for which polynomials this structure exists, and they gave a simple method of preconditioning polynomials to endow them with that structure.[2]
Notes
- ^ Knuth, Donald (December 1962). "Evaluation of polynomials by computer". Communications of the ACM. 5 (12): 595–599. doi:10.1145/355580.369074. Retrieved 25 July 2025.
- ^ Eve, J. (December 1964). "The evaluation of polynomials". Numerische Mathematik. 6 (1): 17–21. doi:10.1007/BF01386049. Retrieved 25 July 2025.
References
- Muller, Jean-Michel (17 November 2016). Elementary functions: Algorithms and implementation. Boston, MA: Birkhäuser Boston. pp. 82–84. doi:10.1007/978-1-4899-7983-4_5. ISBN 978-1-4899-7983-4. Retrieved 25 July 2025.
- Overill, Richard (12 June 1997). "Data parallel evaluation of univariate polynomials by the Knuth-Eve algorithm". Parallel Computing. 23 (13): 2115–2127. doi:10.1016/S0167-8191(97)00096-3. Retrieved 25 July 2025.
- Mesztenyi, C. (January 1967). "Stable evaluation of polynomials". Journal of Research of the National Bureau of Standards - B. Mathematics and Mathematical Physics. 71B (1): 11–17. doi:10.6028/jres.071B.003. Retrieved 25 July 2025.
- Erickson, Jeff. "Evaluating polynomials" (PDF). CS 497: Concrete Models of Computation. University of Illinois Urbana-Champaign. Retrieved 25 July 2025.