@subtitle An open framework for symbolic computation within the C++ programming language
@subtitle @value{UPDATED}
@author The GiNaC Group:
-@author Christian Bauer, Alexander Frink, Richard Kreckel
+@author Christian Bauer, Alexander Frink, Richard Kreckel, Jens Vollinga
@page
@vskip 0pt plus 1filll
* Matrices:: Matrices.
* Indexed objects:: Handling indexed quantities.
* Non-commutative objects:: Algebras with non-commutative products.
+* Hash Maps:: A faster alternative to std::map<>.
@end menu
@cindex hierarchy of classes
@cindex atom
-Symbols are for symbolic manipulation what atoms are for chemistry. You
-can declare objects of class @code{symbol} as any other object simply by
-saying @code{symbol x,y;}. There is, however, a catch in here having to
-do with the fact that C++ is a compiled language. The information about
-the symbol's name is thrown away by the compiler but at a later stage
-you may want to print expressions holding your symbols. In order to
-avoid confusion GiNaC's symbols are able to know their own name. This
-is accomplished by declaring its name for output at construction time in
-the fashion @code{symbol x("x");}. If you declare a symbol using the
-default constructor (i.e. without string argument) the system will deal
-out a unique name. That name may not be suitable for printing but for
-internal routines when no output is desired it is often enough. We'll
-come across examples of such symbols later in this tutorial.
-
-This implies that the strings passed to symbols at construction time may
-not be used for comparing two of them. It is perfectly legitimate to
-write @code{symbol x("x"),y("x");} but it is likely to lead into
-trouble. Here, @code{x} and @code{y} are different symbols and
-statements like @code{x-y} will not be simplified to zero although the
-output @code{x-x} looks funny. Such output may also occur when there
-are two different symbols in two scopes, for instance when you call a
-function that declares a symbol with a name already existent in a symbol
-in the calling function. Again, comparing them (using @code{operator==}
-for instance) will always reveal their difference. Watch out, please.
+Symbolic indeterminates, or @dfn{symbols} for short, are for symbolic
+manipulation what atoms are for chemistry.
+
+A typical symbol definition looks like this:
+@example
+symbol x("x");
+@end example
+
+This definition actually contains three very different things:
+@itemize
+@item a C++ variable named @code{x}
+@item a @code{symbol} object stored in this C++ variable; this object
+ represents the symbol in a GiNaC expression
+@item the string @code{"x"} which is the name of the symbol, used (almost)
+ exclusively for printing expressions holding the symbol
+@end itemize
+
+Symbols have an explicit name, supplied as a string during construction,
+because in C++, variable names can't be used as values, and the C++ compiler
+throws them away during compilation.
+
+It is possible to omit the symbol name in the definition:
+@example
+symbol x;
+@end example
+
+In this case, GiNaC will assign the symbol an internal, unique name of the
+form @code{symbolNNN}. This won't affect the usability of the symbol but
+the output of your calculations will become more readable if you give your
+symbols sensible names (for intermediate expressions that are only used
+internally such anonymous symbols can be quite useful, however).
+
+Now, here is one important property of GiNaC that differentiates it from
+other computer algebra programs you may have used: GiNaC does @emph{not} use
+the names of symbols to tell them apart, but a (hidden) serial number that
+is unique for each newly created @code{symbol} object. In you want to use
+one and the same symbol in different places in your program, you must only
+create one @code{symbol} object and pass that around. If you create another
+symbol, even if it has the same name, GiNaC will treat it as a different
+indeterminate.
+
+Observe:
+@example
+ex f(int n)
+@{
+ symbol x("x");
+ return pow(x, n);
+@}
+
+int main()
+@{
+ symbol x("x");
+ ex e = f(6);
+
+ cout << e << endl;
+ // prints "x^6" which looks right, but...
+
+ cout << e.degree(x) << endl;
+ // ...this doesn't work. The symbol "x" here is different from the one
+ // in f() and in the expression returned by f(). Consequently, it
+ // prints "0".
+@}
+@end example
+
+One possibility to ensure that @code{f()} and @code{main()} use the same
+symbol is to pass the symbol as an argument to @code{f()}:
+@example
+ex f(int n, const ex & x)
+@{
+ return pow(x, n);
+@}
+
+int main()
+@{
+ symbol x("x");
+
+ // Now, f() uses the same symbol.
+ ex e = f(6, x);
+
+ cout << e.degree(x) << endl;
+ // prints "6", as expected
+@}
+@end example
+
+Another possibility would be to define a global symbol @code{x} that is used
+by both @code{f()} and @code{main()}. If you are using global symbols and
+multiple compilation units you must take special care, however. Suppose
+that you have a header file @file{globals.h} in your program that defines
+a @code{symbol x("x");}. In this case, every unit that includes
+@file{globals.h} would also get its own definition of @code{x} (because
+header files are just inlined into the source code by the C++ preprocessor),
+and hence you would again end up with multiple equally-named, but different,
+symbols. Instead, the @file{globals.h} header should only contain a
+@emph{declaration} like @code{extern symbol x;}, with the definition of
+@code{x} moved into a C++ source file such as @file{globals.cpp}.
+
+A different approach to ensuring that symbols used in different parts of
+your program are identical is to create them with a @emph{factory} function
+like this one:
+@example
+const symbol & get_symbol(const string & s)
+@{
+ static map<string, symbol> directory;
+ map<string, symbol>::iterator i = directory.find(s);
+ if (i != directory.end())
+ return i->second;
+ else
+ return directory.insert(make_pair(s, symbol(s))).first->second;
+@}
+@end example
+
+This function returns one newly constructed symbol for each name that is
+passed in, and it returns the same symbol when called multiple times with
+the same name. Using this symbol factory, we can rewrite our example like
+this:
+@example
+ex f(int n)
+@{
+ return pow(get_symbol("x"), n);
+@}
+
+int main()
+@{
+ ex e = f(6);
+
+ // Both calls of get_symbol("x") yield the same symbol.
+ cout << e.degree(get_symbol("x")) << endl;
+ // prints "6"
+@}
+@end example
+
+Instead of creating symbols from strings we could also have
+@code{get_symbol()} take, for example, an integer number as its argument.
+In this case, we would probably want to give the generated symbols names
+that include this number, which can be accomplished with the help of an
+@code{ostringstream}.
+
+In general, if you're getting weird results from GiNaC such as an expression
+@samp{x-x} that is not simplified to zero, you should check your symbol
+definitions.
+
+As we said, the names of symbols primarily serve for purposes of expression
+output. But there are actually two instances where GiNaC uses the names for
+identifying symbols: When constructing an expression from a string, and when
+recreating an expression from an archive (@pxref{Input/Output}).
+
+In addition to its name, a symbol may contain a special string that is used
+in LaTeX output:
+@example
+symbol x("x", "\\Box");
+@end example
+
+This creates a symbol that is printed as "@code{x}" in normal output, but
+as "@code{\Box}" in LaTeX code (@xref{Input/Output}, for more
+information about the different output formats of expressions in GiNaC).
+GiNaC automatically creates proper LaTeX code for symbols having names of
+greek letters (@samp{alpha}, @samp{mu}, etc.).
+
+@cindex @code{subs()}
+Symbols in GiNaC can't be assigned values. If you need to store results of
+calculations and give them a name, use C++ variables of type @code{ex}.
+If you want to replace a symbol in an expression with something else, you
+can invoke the expression's @code{.subs()} method
+(@pxref{Substituting Expressions}).
@cindex @code{realsymbol()}
-Symbols are expected to stand in for complex values by default, i.e. they live
+By default, symbols are expected to stand in for complex values, i.e. they live
in the complex domain. As a consequence, operations like complex conjugation,
-for example (see @ref{Complex Conjugation}), do @emph{not} evaluate if applied
+for example (@pxref{Complex Conjugation}), do @emph{not} evaluate if applied
to such symbols. Likewise @code{log(exp(x))} does not evaluate to @code{x},
because of the unknown imaginary part of @code{x}.
On the other hand, if you are sure that your symbols will hold only real values, you
the domain of the symbol. Instead of @code{symbol x("x");} you can write
@code{realsymbol x("x");} to tell GiNaC that @code{x} stands in for real values.
-@cindex @code{subs()}
-Although symbols can be assigned expressions for internal reasons, you
-should not do it (and we are not going to tell you how it is done). If
-you want to replace a symbol with something else in an expression, you
-can use the expression's @code{.subs()} method (@pxref{Substituting Expressions}).
-
@node Numbers, Constants, Symbols, Basic Concepts
@c node-name, next, previous, up
@end multitable
@end cartouche
+@subsection Numeric functions
+
+The following functions can be applied to @code{numeric} objects and will be
+evaluated immediately:
+
+@cartouche
+@multitable @columnfractions .30 .70
+@item @strong{Name} @tab @strong{Function}
+@item @code{inverse(z)}
+@tab returns @math{1/z}
+@cindex @code{inverse()} (numeric)
+@item @code{pow(a, b)}
+@tab exponentiation @math{a^b}
+@item @code{abs(z)}
+@tab absolute value
+@item @code{real(z)}
+@tab real part
+@cindex @code{real()}
+@item @code{imag(z)}
+@tab imaginary part
+@cindex @code{imag()}
+@item @code{csgn(z)}
+@tab complex sign (returns an @code{int})
+@item @code{numer(z)}
+@tab numerator of rational or complex rational number
+@item @code{denom(z)}
+@tab denominator of rational or complex rational number
+@item @code{sqrt(z)}
+@tab square root
+@item @code{isqrt(n)}
+@tab integer square root
+@cindex @code{isqrt()}
+@item @code{sin(z)}
+@tab sine
+@item @code{cos(z)}
+@tab cosine
+@item @code{tan(z)}
+@tab tangent
+@item @code{asin(z)}
+@tab inverse sine
+@item @code{acos(z)}
+@tab inverse cosine
+@item @code{atan(z)}
+@tab inverse tangent
+@item @code{atan(y, x)}
+@tab inverse tangent with two arguments
+@item @code{sinh(z)}
+@tab hyperbolic sine
+@item @code{cosh(z)}
+@tab hyperbolic cosine
+@item @code{tanh(z)}
+@tab hyperbolic tangent
+@item @code{asinh(z)}
+@tab inverse hyperbolic sine
+@item @code{acosh(z)}
+@tab inverse hyperbolic cosine
+@item @code{atanh(z)}
+@tab inverse hyperbolic tangent
+@item @code{exp(z)}
+@tab exponential function
+@item @code{log(z)}
+@tab natural logarithm
+@item @code{Li2(z)}
+@tab dilogarithm
+@item @code{zeta(z)}
+@tab Riemann's zeta function
+@item @code{tgamma(z)}
+@tab gamma function
+@item @code{lgamma(z)}
+@tab logarithm of gamma function
+@item @code{psi(z)}
+@tab psi (digamma) function
+@item @code{psi(n, z)}
+@tab derivatives of psi function (polygamma functions)
+@item @code{factorial(n)}
+@tab factorial function @math{n!}
+@item @code{doublefactorial(n)}
+@tab double factorial function @math{n!!}
+@cindex @code{doublefactorial()}
+@item @code{binomial(n, k)}
+@tab binomial coefficients
+@item @code{bernoulli(n)}
+@tab Bernoulli numbers
+@cindex @code{bernoulli()}
+@item @code{fibonacci(n)}
+@tab Fibonacci numbers
+@cindex @code{fibonacci()}
+@item @code{mod(a, b)}
+@tab modulus in positive representation (in the range @code{[0, abs(b)-1]} with the sign of b, or zero)
+@cindex @code{mod()}
+@item @code{smod(a, b)}
+@tab modulus in symmetric representation (in the range @code{[-iquo(abs(b)-1, 2), iquo(abs(b), 2)]})
+@cindex @code{smod()}
+@item @code{irem(a, b)}
+@tab integer remainder (has the sign of @math{a}, or is zero)
+@cindex @code{irem()}
+@item @code{irem(a, b, q)}
+@tab integer remainder and quotient, @code{irem(a, b, q) == a-q*b}
+@item @code{iquo(a, b)}
+@tab integer quotient
+@cindex @code{iquo()}
+@item @code{iquo(a, b, r)}
+@tab integer quotient and remainder, @code{r == a-iquo(a, b)*b}
+@item @code{gcd(a, b)}
+@tab greatest common divisor
+@item @code{lcm(a, b)}
+@tab least common multiple
+@end multitable
+@end cartouche
+
+Most of these functions are also available as symbolic functions that can be
+used in expressions (@pxref{Mathematical functions}) or, like @code{gcd()},
+as polynomial algorithms.
+
@subsection Converting numbers
Sometimes it is desirable to convert a @code{numeric} object back to a
algorithm that is likely (but not guaranteed) to give the result most
quickly.
-@cindex @code{inverse()}
+@cindex @code{inverse()} (matrix)
@cindex @code{solve()}
Matrices may also be inverted using the @code{ex matrix::inverse()}
method and linear systems may be solved with:
of the metric tensor.
-@node Non-commutative objects, Methods and Functions, Indexed objects, Basic Concepts
+@node Non-commutative objects, Hash Maps, Indexed objects, Basic Concepts
@c node-name, next, previous, up
@section Non-commutative objects
e = canonicalize_clifford(e);
cout << e << endl;
- // -> 2*eta~mu~nu
+ // -> 2*ONE*eta~mu~nu
@}
@end example
@end example
-@node Methods and Functions, Information About Expressions, Non-commutative objects, Top
+@node Hash Maps, Methods and Functions, Non-commutative objects, Basic Concepts
+@c node-name, next, previous, up
+@section Hash Maps
+@cindex hash maps
+@cindex @code{exhashmap} (class)
+
+For your convenience, GiNaC offers the container template @code{exhashmap<T>}
+that can be used as a drop-in replacement for the STL
+@code{std::map<ex, T, ex_is_less>}, using hash tables to provide faster,
+typically constant-time, element look-up than @code{map<>}.
+
+@code{exhashmap<>} supports all @code{map<>} members and operations, with the
+following differences:
+
+@itemize @bullet
+@item
+no @code{lower_bound()} and @code{upper_bound()} methods
+@item
+no reverse iterators, no @code{rbegin()}/@code{rend()}
+@item
+no @code{operator<(exhashmap, exhashmap)}
+@item
+the comparison function object @code{key_compare} is hardcoded to
+@code{ex_is_less}
+@item
+the constructor @code{exhashmap(size_t n)} allows specifying the minimum
+initial hash table size (the actual table size after construction may be
+larger than the specified value)
+@item
+the method @code{size_t bucket_count()} returns the current size of the hash
+table
+@item
+@code{insert()} and @code{erase()} operations invalidate all iterators
+@end itemize
+
+
+@node Methods and Functions, Information About Expressions, Hash Maps, Top
@c node-name, next, previous, up
@chapter Methods and Functions
@cindex polynomial
* Series Expansion:: Taylor and Laurent expansion.
* Symmetrization::
* Built-in Functions:: List of predefined mathematical functions.
+* Multiple polylogarithms::
+* Complex Conjugation::
+* Built-in Functions:: List of predefined mathematical functions.
* Solving Linear Systems of Equations::
* Input/Output:: Input and output of expressions.
@end menu
@multitable @columnfractions .30 .70
@item @strong{Flag} @tab @strong{Returns true if the object is@dots{}}
@item @code{numeric}
-@tab @dots{}a number (same as @code{is_<numeric>(...)})
+@tab @dots{}a number (same as @code{is_a<numeric>(...)})
@item @code{real}
@tab @dots{}a real integer, rational or float (i.e. is not complex)
@item @code{rational}
@subsection Accessing subexpressions
-@cindex @code{nops()}
-@cindex @code{op()}
@cindex container
-@cindex @code{relational} (class)
-GiNaC provides the two methods
+Many GiNaC classes, like @code{add}, @code{mul}, @code{lst}, and
+@code{function}, act as containers for subexpressions. For example, the
+subexpressions of a sum (an @code{add} object) are the individual terms,
+and the subexpressions of a @code{function} are the function's arguments.
+
+@cindex @code{nops()}
+@cindex @code{op()}
+GiNaC provides several ways of accessing subexpressions. The first way is to
+use the two methods
@example
size_t ex::nops();
ex ex::op(size_t i);
@end example
-for accessing the subexpressions in the container-like GiNaC classes like
-@code{add}, @code{mul}, @code{lst}, and @code{function}. @code{nops()}
-determines the number of subexpressions (@samp{operands}) contained, while
-@code{op()} returns the @code{i}-th (0..@code{nops()-1}) subexpression.
-In the case of a @code{power} object, @code{op(0)} will return the basis
-and @code{op(1)} the exponent. For @code{indexed} objects, @code{op(0)}
-is the base expression and @code{op(i)}, @math{i>0} are the indices.
+@code{nops()} determines the number of subexpressions (operands) contained
+in the expression, while @code{op(i)} returns the @code{i}-th
+(0..@code{nops()-1}) subexpression. In the case of a @code{power} object,
+@code{op(0)} will return the basis and @code{op(1)} the exponent. For
+@code{indexed} objects, @code{op(0)} is the base expression and @code{op(i)},
+@math{i>0} are the indices.
-The left-hand and right-hand side expressions of objects of class
-@code{relational} (and only of these) can also be accessed with the methods
+@cindex iterators
+@cindex @code{const_iterator}
+The second way to access subexpressions is via the STL-style random-access
+iterator class @code{const_iterator} and the methods
+
+@example
+const_iterator ex::begin();
+const_iterator ex::end();
+@end example
+
+@code{begin()} returns an iterator referring to the first subexpression;
+@code{end()} returns an iterator which is one-past the last subexpression.
+If the expression has no subexpressions, then @code{begin() == end()}. These
+iterators can also be used in conjunction with non-modifying STL algorithms.
+
+Here is an example that (non-recursively) prints the subexpressions of a
+given expression in three different ways:
+
+@example
+@{
+ ex e = ...
+
+ // with nops()/op()
+ for (size_t i = 0; i != e.nops(); ++i)
+ cout << e.op(i) << endl;
+
+ // with iterators
+ for (const_iterator i = e.begin(); i != e.end(); ++i)
+ cout << *i << endl;
+
+ // with iterators and STL copy()
+ std::copy(e.begin(), e.end(), std::ostream_iterator<ex>(cout, "\n"));
+@}
+@end example
+
+@cindex @code{const_preorder_iterator}
+@cindex @code{const_postorder_iterator}
+@code{op()}/@code{nops()} and @code{const_iterator} only access an
+expression's immediate children. GiNaC provides two additional iterator
+classes, @code{const_preorder_iterator} and @code{const_postorder_iterator},
+that iterate over all objects in an expression tree, in preorder or postorder,
+respectively. They are STL-style forward iterators, and are created with the
+methods
+
+@example
+const_preorder_iterator ex::preorder_begin();
+const_preorder_iterator ex::preorder_end();
+const_postorder_iterator ex::postorder_begin();
+const_postorder_iterator ex::postorder_end();
+@end example
+
+The following example illustrates the differences between
+@code{const_iterator}, @code{const_preorder_iterator}, and
+@code{const_postorder_iterator}:
+
+@example
+@{
+ symbol A("A"), B("B"), C("C");
+ ex e = lst(lst(A, B), C);
+
+ std::copy(e.begin(), e.end(),
+ std::ostream_iterator<ex>(cout, "\n"));
+ // @{A,B@}
+ // C
+
+ std::copy(e.preorder_begin(), e.preorder_end(),
+ std::ostream_iterator<ex>(cout, "\n"));
+ // @{@{A,B@},C@}
+ // @{A,B@}
+ // A
+ // B
+ // C
+
+ std::copy(e.postorder_begin(), e.postorder_end(),
+ std::ostream_iterator<ex>(cout, "\n"));
+ // A
+ // B
+ // @{A,B@}
+ // C
+ // @{@{A,B@},C@}
+@}
+@end example
+
+@cindex @code{relational} (class)
+Finally, the left-hand side and right-hand side expressions of objects of
+class @code{relational} (and only of these) can also be accessed with the
+methods
@example
ex ex::lhs();
@node Numerical Evaluation, Substituting Expressions, Information About Expressions, Methods and Functions
@c node-name, next, previous, up
-@section Numercial Evaluation
+@section Numerical Evaluation
@cindex @code{evalf()}
GiNaC keeps algebraic expressions, numbers and constants in their exact form.
@}
@end example
+Alternatively, you could use pre- or postorder iterators for the tree
+traversal:
+
+@example
+lst gather_indices(const ex & e)
+@{
+ gather_indices_visitor v;
+ for (const_preorder_iterator i = e.preorder_begin();
+ i != e.preorder_end(); ++i) @{
+ i->accept(v);
+ @}
+ return v.get_result();
+@}
+@end example
+
@node Polynomial Arithmetic, Rational Expressions, Visitors and Tree Traversal, Methods and Functions
@c node-name, next, previous, up
@example
@{
- symbol a("a"), b("b"), c("c");
+ symbol a("a"), b("b"), c("c"), x("x");
idx i(symbol("i"), 3);
ex e = pow(sin(x) - cos(x), 4);
@}
@end example
-@node Built-in Functions, Complex Conjugation, Symmetrization, Methods and Functions
+@node Built-in Functions, Multiple polylogarithms, Symmetrization, Methods and Functions
@c node-name, next, previous, up
@section Predefined mathematical functions
@c
@item @code{psi(n, x)}
@tab derivatives of psi function (polygamma functions)
@item @code{factorial(n)}
-@tab factorial function
+@tab factorial function @math{n!}
@cindex @code{factorial()}
-@item @code{binomial(n, m)}
+@item @code{binomial(n, k)}
@tab binomial coefficients
@cindex @code{binomial()}
@item @code{Order(x)}
standard incorporate these functions in the complex domain in a manner
compatible with C99.
+@node Multiple polylogarithms, Complex Conjugation, Built-in Functions, Methods and Functions
+@c node-name, next, previous, up
@subsection Multiple polylogarithms
@cindex polylogarithm
@cite{Special Values of Multiple Polylogarithms},
J.Borwein, D.Bradley, D.Broadhurst, P.Lisonek, Trans.Amer.Math.Soc. 353/3 (2001), pp. 907-941
-@node Complex Conjugation, Solving Linear Systems of Equations, Built-in Functions, Methods and Functions
+@node Complex Conjugation, Solving Linear Systems of Equations, Multiple polylogarithms, Methods and Functions
@c node-name, next, previous, up
@section Complex Conjugation
@c
git://www.ginac.de / ginac.git / blobdiff