1. Do not use expand if you want anything to be fast.
2. assume you have two large polynomials P and Q.
let pp: rat(P)$
qq: rat(Q)$
then time
ss: pp*qq $ this should be expanded fully into a "recursive" form.
If you want to see it displayed as a sum of monomials, try
ratexpand(ss)$ which is just a display hack.
You can compare this to
fasttimes(pp,qq)
and see if that is faster than pp*qq
I'd be curious to see what you find for your polynomials.
You can also try
divide(pp,qq,x) where x is the main variable, and see
what happens.
divide does not use fasttimes (or the internal lisp program
that does Karatsuba) probably because it is not usually
fast. Though for large enough inputs it might be.
If timings come out the way I think they will, we should
try to figure out a way to explain to people how to make
programs faster (number 1 on my list is "don't use the
expand command". Try ratexpand, or just use rat() forms
and let contagion work.) Maybe add it to some manual or
introductory material.
RJf
Fabrizio Caruso wrote:
>I tested
>
>"expand(rat(..)*rat(...))"
>against
>"fasttimes(rat(...),rat(...))"
>
>with univiariate dense polynoimals
>and "fasttimes" is much faster than the
>operator "*" in all the non-trivial examples
>I have used.
>
>
>It would be nice to have
>"fastquotient" in Maxima, which
>would do something like fasttimes.
>
>I will probably implement it but my implementation
>will use lists or arrays instead of CRE because I don't
>know how to use CRE at low level.
>
>"quotient" and "divide" most probably
>do not use fasttimes internally because they take
>arguments in general form.
>
> Fabrizio
>
>
>
>
>
>
>
>On Wed, 8 Feb 2006, Richard Fateman wrote:
>
>
>
>>expand( ...*....) is always very slow. It does lots of things that have
>>nothing to do with polynomials, e.g. diff.
>>try rat(...* ....) if you want speed. or ratsimp() if you want the results
>>in
>>non-CRE form.
>>
>>Probably you should keep your items in CRE form (that is, use rat() on
>>them).
>>RJF
>>
>>----- Original Message -----
>>From: "Fabrizio Caruso" <caruso at posso.dm.unipi.it>
>>To: "Richard Fateman" <fateman at cs.berkeley.edu>
>>Sent: Wednesday, February 08, 2006 7:57 AM
>>Subject: Re: [Maxima] fastquotient?
>>
>>
>>
>>
>>>Hi!
>>>
>>>I need to compute within my Maxima package
>>>the quotient but the remainder might be non-zero so I need
>>>something like "quotient" but faster than "quotient".
>>>Exact division would mean assuming a zero-remainder
>>>which might lead to wrong results if used
>>>to compute the quotient.
>>>
>>>If this is not available in Maxima my suggestion
>>>would be to implement it as multiplication by
>>>the modular inverse.
>>>
>>>In all my tests "fasttimes" is much faster than doing
>>>the product of two polynomials by "expand(...*...)"
>>>even if the polynomials are univariate.
>>>
>>> Regards
>>>
>>> Fabrizio
>>>
>>>On Wed, 8 Feb 2006, Richard Fateman wrote:
>>>
>>>
>>>
>>>>----- Original Message -----
>>>>From: "Fabrizio Caruso" <caruso at posso.dm.unipi.it>
>>>>To: <maxima at math.utexas.edu>
>>>>Sent: Wednesday, February 08, 2006 6:39 AM
>>>>Subject: fastquotient?
>>>>
>>>>
>>>>
>>>>
>>>>>Hi all again!
>>>>>
>>>>>Is there in Maxima a function to divide
>>>>>polynoimals in CRE faster than "divide"?
>>>>>
>>>>>
>>>>Divide probably converts its arguments to CRE. Do
>>>>you want quotient or remainder? Or exact division?
>>>>I guess if you are in a hurry for the answer, and you have
>>>>univariate polynomials you might consider a program that
>>>>does nothing else, and may be faster. NTL is one such
>>>>program.
>>>>
>>>>
>>>>
>>>>>I mean something equivalent to "fasttimes",
>>>>>(it could be implemented by multiplication
>>>>>by the modular inverse).
>>>>>
>>>>>
>>>>I think this would work for exact division; knowing that
>>>>you can do exact division requires a GCD which may be,
>>>>in practice, the more expensive item.
>>>>
>>>>
>>>>>Is fasttimes using Karatsuba or something else?
>>>>>
>>>>>
>>>>Karatsuba (division into two pieces, recursively)
>>>>
>>>>
>>>>>If so, why does the documentation say that the
>>>>>arguments of "fasttimes" must be multivariate?
>>>>>
>>>>>
>>>>I think that testing showed that for one variable it
>>>>was not faster, at least when it was written (in 1970 or so).
>>>>It may be different now.
>>>>
>>>>RJF
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>
>>
>
>
>