Barton,
Thanks for investigating.
> To evaluate sum(a[i],i,1,n), Maxima calls
> great n^3 / 6 - n / 6 times (experimentally determined).
> Surely even a simple-minded algorithm would be O(n^2).
After glancing at src/asum.lisp I think the problem with
sum(a[i],i,1,n) is that the partial sum is resimplified after
each term is added.
However simplification handles 'sum(a[i],i,1,n) and in that
case the time scales like n^2, I find.
Evaluation of finite sums is handled by DOSUM and
simplification of finite sums is handled by SIMPSUM1
(both in src/asum.lisp). At this late date I don't see a good
reason for two implementations of the finite sum code;
I rewrote that code last year and probably I was trying
to preserve the existing organization.
Probably the short-term fix is to avoid resimplifying the
partial sum in DOSUM. A longer term fix is to merge the
finite sum code from DOSUM and SIMPSUM1.
Robert