Possible memory leak? (was: update on fast mult benchmark (fwd))

[Richard Fateman]

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