JavaScript is disabled for your browser. Some features of this site may not work without it.
On the Computation of Powers of a Class of Polynomials

Author
Horowitz, Ellis; Sahni, Sartaj
Abstract
A general class of polynomials is defined which includes as subcases sparse and dense polynomials. For any polynomial $P$ within this class a host of algorithms are analyzed for computing $P^{n}$. While the Homomorphism algorithm is superior on dense polynomials it is shown that for sufficiently sparse polynomials, iteration is more efficient. A simple rule that takes linear time is given for deciding when it is advisable to use either one of these algorithms. Keywords: Polynomial Powers, sparse polynomials, modular algorithms.
Date Issued
1972-08Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR72-143
Type
technical report