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

[Richard B. Kreckel]

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/>