X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=blobdiff_plain;f=doc%2Ftutorial%2Fginac.texi;h=b58d631b868143183d24b5777441e7d17e93ae61;hp=8d2f985ec729cdc2854a42f98795bfd938c7b283;hb=b5483c25af5d84095ca647390914e3fb63ad96a0;hpb=77ab8cc26b361fab2e8e13d278fcdbeea9b0ddf0 diff --git a/doc/tutorial/ginac.texi b/doc/tutorial/ginac.texi index 8d2f985e..b58d631b 100644 --- a/doc/tutorial/ginac.texi +++ b/doc/tutorial/ginac.texi @@ -48,7 +48,7 @@ notice identical to this one. @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 @@ -685,6 +685,7 @@ meta-class for storing all mathematical objects. * 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 @@ -952,35 +953,175 @@ $\sin 2x$ @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 directory; + map::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 @@ -988,12 +1129,6 @@ would like to have such functions evaluated. Therefore GiNaC allows you to speci 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 @@ -1204,6 +1339,120 @@ can be applied is listed in the following table. @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 @@ -1764,15 +2013,17 @@ more information about using matrices with indices, and about indices in general. The @code{matrix} class provides a couple of additional methods for -computing determinants, traces, and characteristic polynomials: +computing determinants, traces, characteristic polynomials and ranks: @cindex @code{determinant()} @cindex @code{trace()} @cindex @code{charpoly()} +@cindex @code{rank()} @example ex matrix::determinant(unsigned algo=determinant_algo::automatic) const; ex matrix::trace() const; ex matrix::charpoly(const ex & lambda) const; +unsigned matrix::rank() const; @end example The @samp{algo} argument of @code{determinant()} allows to select @@ -1784,7 +2035,7 @@ file. By default, GiNaC uses a heuristic to automatically select an 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: @@ -2536,7 +2787,7 @@ one form for @samp{F} and explicitly multiply it with a matrix representation 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 @@ -2828,7 +3079,7 @@ You can use this to compare two expressions or for further simplifications: e = canonicalize_clifford(e); cout << e << endl; - // -> 2*eta~mu~nu + // -> 2*ONE*eta~mu~nu @} @end example @@ -2946,7 +3197,43 @@ standing. For 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} +that can be used as a drop-in replacement for the STL +@code{std::map}, 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 @@ -2999,6 +3286,9 @@ avoided. * 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 @@ -3075,7 +3365,7 @@ table: @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_(...)}) +@tab @dots{}a number (same as @code{is_a(...)}) @item @code{real} @tab @dots{}a real integer, rational or float (i.e. is not complex) @item @code{rational} @@ -3146,28 +3436,117 @@ for an explanation of these. @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(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(cout, "\n")); + // @{A,B@} + // C + + std::copy(e.preorder_begin(), e.preorder_end(), + std::ostream_iterator(cout, "\n")); + // @{@{A,B@},C@} + // @{A,B@} + // A + // B + // C + + std::copy(e.postorder_begin(), e.postorder_end(), + std::ostream_iterator(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(); @@ -3274,7 +3653,7 @@ after @code{other}. @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. @@ -4093,6 +4472,21 @@ lst gather_indices(const ex & e) @} @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 @@ -4251,7 +4645,7 @@ constants, functions and indexed objects as well: @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); @@ -4755,7 +5149,7 @@ almost any kind of object (anything that is @code{subs()}able): @} @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 @@ -4858,9 +5252,9 @@ GiNaC contains the following predefined mathematical functions: @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)} @@ -4885,6 +5279,8 @@ serious CAS. It is to be expected that future revisions of the C++ 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 @@ -5031,7 +5427,7 @@ E.Remiddi, J.A.M.Vermaseren, Int.J.Mod.Phys. A15 (2000), pp. 725-754 @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