[sage-devel] GiNaC as the symbolic manipulation engine in Sage

2008/8/12 Barton Willis <willisb at unk.edu>:
> -----maxima-bounces at math.utexas.edu wrote: -----
>
>>In the case of the summation problem mentioned in this thread,
>>the central problem is that Maxima's simplification algorithm
>>for the result (something of the form (x + y)^2 + (x + y)^4 + ...)
>>seems to run in n^2 time where n is the number of terms.
>
> Simplus doesn't take advantage of sorting (sorting places common
> terms next to each other); so
>
> (%i2) tree_reduce("+", makelist((x+y)^(2*i),i,1,10000))$
> Evaluation took 0.4000 seconds (0.4000 elapsed)
>
> Here's a simple alternative simplus that makes xreduce faster
> than tree_reduce for this sum: (simplus-prosaic is not in Maxima)
>
> (%i3) load("/mysimp/simplus-prosaic.o")$
>
> (%i4) xreduce("+", makelist((x+y)^(2*i),i,1,10000))$
> Evaluation took 0.3700 seconds (0.3700 elapsed)
>
> Back to a fresh maxima:
>
> (%i3) xreduce("+", makelist((x+y)^(2*i),i,1,10000))$
> Evaluation took 31.5000 seconds (31.5000 elapsed)

Maybe the sum algorithm (dosum in asum.lisp) should be improved.
Something like my_sum should not be to hard to implement:

(%i1) my_sum(expr, i, lo, hi) :=
    if hi=lo then subst(i=lo, expr)
    else if hi-lo=1 then subst(i=lo, expr) + subst(i=hi, expr)
    else block(
        [lo1 : floor((hi+lo)/2)],
        my_sum(expr, i, lo, lo1) + my_sum(expr, i, lo1+1, hi)
    )$
(%i2) showtime:all$
Evaluation took 0.0000 seconds (0.0000 elapsed)

(%i3) tree_reduce("+", makelist((x+y)^(2*i), i, 1, 10000))$
Evaluation took 0.5510 seconds (0.5560 elapsed)

(%i4) my_sum((x+y)^(2*i), i, 0, 10000)$
Evaluation took 0.9770 seconds (0.9820 elapsed)

(%i5) compile(my_sum)$
(%i6) my_sum((x+y)^(2*i), i, 0, 10000)$
Evaluation took 0.3410 seconds (0.3490 elapsed)

(%i7) sum((x+y)^(2*i), i, 0, 10000)$
Evaluation took 57.7640 seconds (57.9480 elapsed)

(%i9) %o6-%o7;
Evaluation took 118.2390 seconds (118.9120 elapsed)
(%o9) 0

Of course %o9 is bad too.

-- 
Andrej