A.2 Internal representation of products and sums

Although it should be completely transparent for the user of GiNaC a short discussion of this topic helps to understand the sources and also explain performance to a large degree. Consider the unexpanded symbolic expression 2*d^3*(4*a+5*b-3) which could naively be represented by a tree of linear containers for addition and multiplication, one container for exponentiation with base and exponent and some atomic leaves of symbols and numbers in this fashion:

However, doing so results in a rather deeply nested tree which will quickly become inefficient to manipulate. We can improve on this by representing the sum as a sequence of terms, each one being a pair of a purely numeric multiplicative coefficient and its rest. In the same spirit we can store the multiplication as a sequence of terms, each having a numeric exponent and a possibly complicated base, the tree becomes much more flat:

The number 3 above the symbol d shows that mul objects are treated similarly where the coefficients are interpreted as exponents now. Addition of sums of terms or multiplication of products with numerical exponents can be coded to be very efficient with such a pair-wise representation. Internally, this handling is performed by most CAS in this way. It typically speeds up manipulations by an order of magnitude. The overall multiplicative factor 2 and the additive term -3 look somewhat out of place in this representation, however, since they are still carrying a trivial exponent and multiplicative factor 1 respectively. Within GiNaC, this is avoided by adding a field that carries an overall numeric coefficient. This results in the realistic picture of internal representation for 2*d^3*(4*a+5*b-3):

This also allows for a better handling of numeric radicals, since sqrt(2) can now be carried along calculations. Now it should be clear, why both classes add and mul are derived from the same abstract class: the data representation is the same, only the semantics differs. In the class hierarchy, methods for polynomial expansion and the like are reimplemented for add and mul, but the data structure is inherited from expairseq.