JavaScript is disabled for your browser. Some features of this site may not work without it.
Algorthms for Rational Function Arithmetic Operations

Author
Horowitz, Ellis
Abstract
Despite recent advances in speeding up many arithmetic and algebraic algorithms plus an increased concern with algorithm analysis, no computing time study has ever been done for algorithms which perform the rational function arithmetic operations. Mathematical symbol manipulation systems which provide for operations on rational functions use algorithms which were initially given by P. Henrici in 1956. In this paper, these algorithms are precisely specified and their computing times analyzed. Then new algorithms based on the use of modular arithmetic are developed and analyzed. It is shown that the computing time for adding and taking the derivative of univariate rational functions is 2 orders of magnitude faster using the modular algorithms. Also, the computing time for rational function multiplication will be one order of magnitude faster using the modular algorithm. The new method is generalized to the multivariate case and extensive empirical results are given. Keywords: Rational functions, modular arithmetic, arithmetic oeprations, algebraic algorithms.
Date Issued
1971-11Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR71-112
Type
technical report