Form is really slow and fast for me. What could this mean?

[Richard Fateman]

My guess is that in Form when you write
Local q=(1+x+y+z)^40
what is produced is some internal encoded form
that is inadequate for addition of polynomials,
but is somehow adequate to know how many terms there
are.
 Form, in its devotion to handling large expressions,
is not so efficient on adding this expression which has "only"
13,000 terms and can be handled by other computer
algebra systems.  (Like a page-oriented sort).

But this may be entirely wrong.

If the review article is something I wrote, (I wrote
2 papers on polynomial powering: sparse and dense),
I'll try to get it on line.
RJF


"Richard B. Kreckel" wrote:
> 
> Hi,
> 
> On Fri, 29 Mar 2002, parisse wrote:
> > Richard Fateman wrote:
> >
> > > It is not necessary to have two .sorts in there.
> > > I took out the first one, and it was just as fast.
> > > Why should this help?
> > >
> > > I tried this:
> > >
> > > Symbols x,y,z;
> > > Local q=(1+x+y+z)^20*(1+(1+z+x+y)^20)-(1+x+z+y)^20*(1+(1+z+x+y)^20);
> > > Print;
> > > .end
> > >
> > > and it took about twice as long as the longest time.
> > > (190 seconds)
> > >
> > > I also tried
> > > Local q=(1+x+y+z)^40
> > >   and that takes about .98 seconds
> > > Local q=(1+x+y+z)^40- (1+x+z+y)^40
> > >   and that takes about 1.7 seconds.
> > >
> > > What is going on?
> >
> >
> > Taking the power is much faster simply because you do *not* apply
> > the chinese powering algorithm as a simple cost analysis shows
> > for any multivariate polynomial. Just make the 40* multiplication loop.
> 
> Honestly, I've never heard the term "chinese powering".  I assume you mean
> fast exponentiation (by successively going through the binary
> representation of the integer exponent)?  Sure the multiplication loops
> are much faster.  I guess this is what Knuth means in volume 2, in his
> section "evaluation of powers".  BTW, even faster you can directly build
> up the result with the proper coefficients in place (as GiNaC does in
> power::expand_add(), slightly fixed in CVS, too).
> 
> Errhh, D. Knuth gives a citation of a review article in that section which
> sounds interesting to me.  Since it is quite hard to get, could that be
> made available online by its author or was it prior to electronic
> preparation of manuscripts?   ;-)
> 
> However, I am not sure how that can be the culprit why Form is so slow in
> the second case.  The difference for exponent 20 seems to be a factor of
> ten, based on my own tests.  Certainly not a power of 100 or more...
> 
> Regards
>      -richy.
> --
> Richard B. Kreckel
> <Richard.Kreckel at Uni-Mainz.DE>
> <http://wwwthep.physik.uni-mainz.de/~kreckel/>