Richard B. Kreckel wrote:
Sure Maple bothers to sort! The order may not be apparent, but they do sort their expressions. Hasn't that been the consensus when the discussion last came up on sci.math.symbolic?
I don't call what they do sorting, since they do not impose an external order on expressions: it is merely collecting of terms. This can be done by a hash table in (probably) O(n) time. An answer which does not allow you to tell the degree of a polynomial without looking through all the terms is less useful. A test which requires division would probably show this.
By the way: This observation of yours that Maple gets slower on the 2nd trial, isn't this exactly the problem Carl DeVore was describing in sci.math.symbolic recently? It seems to get even slower after more trials. Is this a new "feature" or do older releases of Maple also suffer from this?
I have no old copies "alive".
[...]
There are not too many ways of multiplying sparse polynomials without using u*v multiplies and about u*v -size(answer) adds.
I was referring more to implementation details than to fundamental algorithmic things. Hence the gazillions. :-)
For dense polynomials in a finite field, FFT can be used. My guess is that an FFT approach would not be faster on such a small ( :) ) problem as this one. But a careful implementation might win. In order to represent the inputs and the outputs, the FFT would probably have to be done quite a few times since the bignum coefficients would need to be built up by Chinese Remainder.
This is exactly what I was thinking when Dan Bernstein recommended the FFT-based method for univariate polynomials when I last met him. I don't know if anything came out of his Zmult project, though...
It would be possible to encode the question and the answer as a huge multiplication of 2 integers. The loss in encoding and decoding would be either very wasteful or very tricky. <snip> RJF