On computing short products
Thom Mulders · 1997
. A polynomial consisting of only the low degree monomials of the (full) product of two univariate polynomials f and g is called a short product of f and g. A global algorithm, independent of the actual multiplication algorithm used, to compute short products is proposed. Its performance for several multiplication algorithms is studied. Also several applications of short products are pointed out. 1. Introduction In [10] efficient algorithms for multiprecision floating point multiplication are developed. The main idea of these algorithms is the fact that, in order to perform such a multiplication, it is not necessary to first perform the full exact multiplication. In fact the products of the least significant digits do (in general) not contribute to the final result. A similar situation occurs when one is computing in the residue ring S = R[x]=(x N ) for some ring R and positive integer N . When F; G 2 S are represented by f; g 2 R[x] (both of degree ! N ), one could compute a repre...