The efficient calculation of powers of polynomials

摘要

Suppose we are given a polynomial P(x1,…,xr) in r≥1 variables, let m bound the degree of P in all variables xi, 1≤i≤r, and we wish to raise P to the nth power, n>1. In a recent paper which compared the iterative versus the binary method it was shown that their respective computing times were O(m2rnr+1) versus O(mn)2r) when using single precision arithmetic. In this paper a new algorithm is given whose computing time is shown to be O((mn)r+1). Also if we allow for polynomials with multiprecision integer coefficients, the new algorithm presented here will be faster by a factor of mr−1nr over the binary method and faster by a factor of mr−1 over the iterative method. Extensive empirical studies of all three methods show that this new algorithm will be superior for polynomials of even relatively small degree, thus guaranteeing a practical as well as a useful result.