The efficient calculation of powers of polynomials

✍ Scribed by Ellis Horowitz

• Book ID: 104148093
• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 476 KB
• Volume: 7
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(73)80003-0

✦ Synopsis

Suppose we are given a polynomial P (xl ,..., x~) in r ~> 1 variables, let m bound the degree of P in all variables x~, 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(m2~n r+l) 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)~+l). Also if we allow for polynomials with multiprecision integer coefficients, the new algorithm presented here will be faster by a factor of mr-in ~ over the binary method and faster by a factor of m T-x 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.