[GiNaC-list] About 'unoptimal' expanding (Was: GiNaC Licensing)

[Ondrej Certik]

On Wed, Oct 22, 2008 at 12:58 PM, Alexei Sheplyakov <varg at theor.jinr.ru> wrote:
> Dear Ondrej,
>
> On Wed, Oct 22, 2008 at 12:16:23AM +0200, Ondrej Certik wrote:
>
>> Ginac is expanding in an unoptimal way though,
>
> Are you sure?
>
> $ cat simple.ginsh
> #!/usr/bin/env ginsh
> e = (x^10+x^9+x^8+x^7+x^6+x^4+x^3+x^2+x+1)*(x-1);
> g = e^10*(e^10+1);
> time(expand(g));
> ./simple.ginsh | tail -n1
> 2.40s
>
> Your "optimal" method runs out of memory:
>
> $ cat smart.ginsh
> #!/usr/bin/env ginsh
> e = (x^10+x^9+x^8+x^7+x^6+x^4+x^3+x^2+x+1)*(x-1);
> g = e^20 + e^10;
> time(expand(g));
> ./smart.ginsh | tail -n1
> St9bad_alloc
> syntax error, unexpected ')' at )
>
> In many calculations the initial and final expressions are (much) smaller
> than intermediate ones. That's why GiNaC tries to to cancel intermediate
> terms as early as possible. Hence 'unoptimal' (bottom-up instead of top-down)
> expand(), eval(), etc.

Right, good example. So it seems to me that there are problems where
one way is better and there are problems where the other way is
bettter? If this is the case, maybe there could be an option to choose
which method to use.

Ondrej