Abstract
A new method for estabhshlng lower bounds on the number of multlphcatlons and divisions reqmred to compute rational functions is described The method is based on combining two known methods, dlmenstonahty and rate of growth The method is apphed to several problems and new lower bounds are obtained.
Original language | English (US) |
---|---|
Pages (from-to) | 582-601 |
Number of pages | 20 |
Journal | Journal of the ACM (JACM) |
Volume | 26 |
Issue number | 3 |
DOIs | |
State | Published - Jul 1 1979 |
Keywords
- algebraic operations
- analysts of algorithms
- computational complexity
- counting methods
- dimensionality
- lower bounds
- multiplications
- optimality
- polynomials
- rate of growth
- rational functions
ASJC Scopus subject areas
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence