> Macsyma probably manages to use worse-case n^2 (or worse)
> algorithms. For example, it tends NOT to do merge (n-items,
> m-items)
Tracing 'great' shows that sum(a[i],i,1,n)+sum(b[i],i,i,n) takes 2*n-1
comparisons. Fully interspersed terms like that are the worst case.
> By putting up firewalls inside simplus and simptimes, the
> change in representation can plausibly be separated from any
> other accesses.
Yes, information hiding here (and elsewhere) would be nice... but a can
of worms to implement. Binary merge would make a significant difference
in speed without requiring any changes to other parts of the code base.
-s