Hi!
Thanks!
Yes, expand was the problem.
fasttimes performs roughly the same as "*"
with fairly big dense univariate
polynomials (degree>2500)
which means fasttimes must be probably
using something different then standard Karatsuba.
I wonder it fasttimes does...
Karatsuba as described in textbooks
splits univariate dense polynomials
into its higher degree part and
lower degree part and by doing so
it avoids one multiplication (3 instead of 4)
at each recursive step.
My C++ implementation of Karatsuba overtakes
on the computers I tested it
the school multiplication algorithm
as soon as the degree is about 100.
Fabrizio
On Wed, 8 Feb 2006, Richard Fateman wrote:
> 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
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>
> >>>
> >>
> >>
> >
> >
> >
>