Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Addition Requirements for Rational Functions

Addition Requirements for Rational Functions

File(s)
75-255.ps (303.25 KB)
75-255.pdf (846 KB)
Permanent Link(s)
https://hdl.handle.net/1813/7322
Collections
Computer Science Technical Reports
Author
Kirkpatrick, David G.
Kedem, Zvi M.
Abstract

A notion of rank or independence for arbitrary sets of rational functions is developed, which bounds from below the number of additions and subtractions required of all straight-line algorithms which compute those functions. This permits a uniform derivation of the best lower bounds known for a number of familiar sets of rational functions. The result is proved without the use of substitution arguments. This not only provides an interesting contrast to standard approaches for arithmetic lower bounds, but also allows the algebraic setting to be somewhat generalized. Keywords: additions, algorithms, analysis of algorithms, arithmetic complexity, computational complexity, dimensionality, lower bounds, matrix multiplication, optimality, polynomials, rational functions.

Date Issued
1975-08
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-255
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance