Bounds on Polynomial Evaluation Algorithms
Abstract
The purpose of the work is to investigate the number of arithmetic operations required by algorithms which evaluate polynomials. Previous results show that a polynomial of degree n requires at least n/2 multiplication/ divisions and at least n addition/subtractions for its evaluation if the coefficients of the polynomial are suitably independent irrational numbers. However, the coefficients of any polynomial that would be evaluated in practice are represented only to a finite accuracy and are therefore rational numbers. The above results are extended to show that the same lower bounds hold for almost all rational polynomials if the polynomial is being evaluated efficiently. Another lower bound result is given that shows that almost all rational polynomials of degree n require at least square root of n multiplication/divisions for their evaluation by any algorithm, efficient or not.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1972
- Accession Number
- AD0740328
Entities
People
- Larry Joseph Stockmeyer
Organizations
- Massachusetts Institute of Technology