[GiNaC-devel] Term ordering.

[Alexei Sheplyakov]

Hi,

> when I do (e.g. in ginsh)
> 
> -a * (r^n-R^n);
> 
> I get
> 
> a * (R^n-r^n)
> 
> for n <= 3
> 
> but
> 
> -a * (r^n-R^n)
> 
> for n > 3

http://www.ginac.de/tutorial/Automatic-evaluation.html#Automatic-evaluation

The terms of sums and products (and some other things like the arguments of
symmetric functions, the indices of symmetric tensors etc.) are re-ordered
into a canonical form that is deterministic, but not lexicographical or in
any other way easy to guess (it almost always depends on the number and order
of the symbols you define). However, constructing the same expression twice,
either implicitly or explicitly, will always result in the same canonical form.


Also note that the canonical form might change from run to run:

for i in `seq 1 100`; do
        echo "a = x; b = y; x - y;" | ginsh
done |  sort -n | uniq
x
x-y
y
-y+x

Depending on luck, canonical form of the same expression (x-y) might be
either 'x-y' or '-y+x' (of course it's the same during one run).

> Why?

The terms of sums (and products) are stored as an array sorted according
to the hash value. Using such a data structure makes collecting similar
terms reasonably fast. As a side effect it makes the order of terms
`unpredictable', that is, deterministic, but not easy to guess (that's
a property of any reasonable hash function).

Please note: this is not a bug. Fast(er) automatic evaluation is much more
important than a pretty output. Given that input and output expressions
typically contain ~ 10^4 terms (or more) the exact term order does not
really matter anyway. If you really need a fancy output, write a custom
printing context.

@developers:

This question pops up quite often [1], should we add it to the FAQ?

[1]

http://www.ginac.de/pipermail/ginac-list/2008-October/001428.html
http://www.ginac.de/pipermail/ginac-list/2008-December/001461.html
http://www.ginac.de/pipermail/ginac-list/2010-April/001598.html

Best regards,
	Alexei