- added one more sample for our friends at NASA. :-)

[ginac.git] / doc / tutorial / tutorial.sgml.in

<!DOCTYPE Book PUBLIC "-//Davenport//DTD DocBook V3.0//EN">

<book>
<title>GiNaC MAJOR_VERSION.MINOR_VERSION Tutorial</title>
<bookinfo>
<subtitle>An open framework for symbolic computation within the C++ programming language</subtitle>
<bookbiblio>
<authorgroup>
  <collab>
    <collabname>The GiNaC Group</collabname>
  </collab>
  <author>
    <firstname>Christian</firstname><surname>Bauer</surname>
    <affiliation>
      <address><email>Christian.Bauer@Uni-Mainz.DE</email></address>
    </affiliation>
  </author>
  <author>
    <firstname>Alexander</firstname><surname>Frink</surname>
    <affiliation>
      <address><email>Alexander.Frink@Uni-Mainz.DE</email></address>
    </affiliation>
  </author>
  <author>
    <firstname>Richard</firstname><othername>B.</othername><surname>Kreckel</surname>
    <affiliation>
      <address><email>Richard.Kreckel@Uni-Mainz.DE</email></address>
    </affiliation>
  </author>
</authorgroup>
</bookbiblio>
</bookinfo>

<preface>
<title>Introduction</title>

<para>The motivation behind GiNaC derives from the observation that
most present day computer algebra systems (CAS) are linguistically and
semantically impoverished.  It is an attempt to overcome the current
situation by extending a well established and standardized computer
language (C++) by some fundamental symbolic capabilities, thus
allowing for integrated systems that embed symbolic manipulations
together with more established areas of computer science (like
computation-intense numeric applications, graphical interfaces, etc.)
under one roof.</para>

<para>This tutorial is intended for the novice user who is new to
GiNaC but already has some background in C++ programming.  However,
since a hand made documentation like this one is difficult to keep in
sync with the development the actual documentation is inside the
sources in the form of comments.  That documentation may be parsed by
one of the many Javadoc-like documentation systems.  If you fail at
generating it you may access it directly at URL <ulink
url="http://www.ginac.de/reference/"><literal>http://www.ginac.de/reference/</literal></ulink>.
It is an invaluable resource not only for the advanced user who wishes
to extend the system (or chase bugs) but for everybody who wants to
comprehend the inner workings of GiNaC.  This little tutorial on the
other hand only covers the basic things that are unlikely to change in
the near future.  </para>

<sect1><title>License</title>

<para>The GiNaC framework for symbolic computation within the C++
programming language is Copyright (C) 1999 Johannes Gutenberg
Universit&auml;t Mainz, Germany.</para>

<para>This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.</para>

<para>This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.</para>

<para>You should have received a copy of the GNU General Public License
along with this program; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
MA 02111-1307, USA.</para>

</preface>

<chapter>
<title>A Tour of GiNaC</title>

<para>This quick tour of GiNaC wants to rise your interest in in the
subsequent chapters by showing off a bit.  Please excuse us if it
leaves many open questions.</para>

<sect1><title>How to use it from within C++</title> <para>The GiNaC
open framework for symbolic computation within the C++ programming
language does not try to define a language of it's own as conventional
CAS do.  Instead, it extends the capabilities of C++ by symbolic
manipulations.  Here is how to generate and print a simple (and
pointless) bivariate polynomial with some large coefficients:
<example>
<title>My first GiNaC program (a bivariate polynomial)</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol x("x"), y("y");
    ex poly;

    for (int i=0; i<3; ++i)
        poly += factorial(i+16)*pow(x,i)*pow(y,2-i);

    cout &lt;&lt; poly &lt;&lt; endl;
    return 0;
}
</programlisting>
<para>Assuming the file is called <literal>hello.cc</literal>, on 
our system we can compile and run it like this:</para>
<screen>
<prompt>$</prompt> c++ hello.cc -o hello -lcln -lginac
<prompt>$</prompt> ./hello
355687428096000*x*y+20922789888000*y^2+6402373705728000*x^2
</screen>
</example>
</para>

<para>Next, there is a more meaningful C++ program that calls a
function which generates Hermite polynomials in a specified free
variable.
<example>
<title>My second GiNaC program (Hermite polynomials)</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

ex HermitePoly(symbol x, int deg)
{
    ex HKer=exp(-pow(x,2));
    // uses the identity H_n(x) == (-1)^n exp(x^2) (d/dx)^n exp(-x^2) 
    return normal(pow(-1,deg) * diff(HKer, x, deg) / HKer);
}

int main()
{
    symbol z("z");

    for (int i=0; i<6; ++i)
        cout &lt;&lt; "H_" &lt;&lt; i &lt;&lt; "(z) == " &lt;&lt; HermitePoly(z,i) &lt;&lt; endl;

    return 0;
}
</programlisting>
<para>When run, this will type out</para>
<screen>
H_0(z) == 1
H_1(z) == 2*z
H_2(z) == 4*z^2-2
H_3(z) == -12*z+8*z^3
H_4(z) == -48*z^2+16*z^4+12
H_5(z) == 120*z-160*z^3+32*z^5
</screen>
</example>
This method of generating the coefficients is of course far from
optimal for production purposes.</para>

<para>In order to show some more examples of what GiNaC can do we
will now use <literal>ginsh</literal>, a simple GiNaC interactive
shell that provides a convenient window into GiNaC's capabilities.
</para></sect1>

<sect1><title>What it can do for you</title>

<para>After invoking <literal>ginsh</literal> one can test and
experiment with GiNaC's features much like in other Computer Algebra
Systems except that it does not provide programming constructs like
loops or conditionals.  For a concise description of the
<literal>ginsh</literal> syntax we refer to its accompanied man-page.
Suffice to say that assignments and comparisons in
<literal>ginsh</literal> are written as they are in C,
i.e. <literal>=</literal> assigns and <literal>==</literal>
compares.</para>

<para>It can manipulate arbitrary precision integers in a very fast
way.  Rational numbers are automatically converted to fractions of
coprime integers:
<screen>
> x=3^150;
369988485035126972924700782451696644186473100389722973815184405301748249
> y=3^149;
123329495011708990974900260817232214728824366796574324605061468433916083
> x/y;
3
> y/x;
1/3
</screen>
</para>

<para>All numbers occuring in GiNaC's expressions can be converted
into floating point numbers with the <literal>evalf</literal> method,
to arbitrary accuracy:
<screen>
> evalf(1/7);
0.14285714285714285714
> Digits=150;
150
> evalf(1/7);
0.1428571428571428571428571428571428571428571428571428571428571428571428
5714285714285714285714285714285714285
</screen>
</para>

<para>Exact numbers other than rationals that can be manipulated in
GiNaC include predefined constants like Archimedes' Pi.  They can both
be used in symbolic manipulations (as an exact number) as well as in
numeric expressions (as an inexact number):
<screen>
> a=Pi^2+x;
x+Pi^2
> evalf(a);
x+9.869604401089358619L0
> x=2;
2
> evalf(a);
11.869604401089358619L0
</screen>
</para>

<para>Built-in functions evaluate immediately to exact numbers if
this is possible.  Conversions that can be safely performed are done
immediately; conversions that are not generally valid are not done:
<screen>
> cos(42*Pi);
1
> cos(acos(x));
x
> acos(cos(x));
acos(cos(x))
</screen>
(Note that converting the last input to <literal>x</literal> would
allow one to conclude that <literal>42*Pi</literal> is equal to
<literal>0</literal>.)</para>

<para>Linear equation systems can be solved along with basic linear
algebra manipulations over symbolic expressions.  In C++ GiNaC offers
a matrix class for this purpose but we can see what it can do using
<literal>ginsh</literal>'s notation of double brackets to type them
in:
<screen>
> lsolve(a+x*y==z,x);
y^(-1)*(z-a);
lsolve([3*x+5*y == 7, -2*x+10*y == -5], [x, y]);
[x==19/8,y==-1/40]
> M = [[ [[1, 3]], [[-3, 2]] ]];
[[ [[1,3]], [[-3,2]] ]]
> determinant(M);
11
> charpoly(M,lambda);
lambda^2-3*lambda+11
</screen>
</para>

<para>Multivariate polynomials and rational functions may be expanded,
collected and normalized (i.e. converted to a ratio of two coprime 
polynomials):
<screen>
> a = x^4 + 2*x^2*y^2 + 4*x^3*y + 12*x*y^3 - 3*y^4;
-3*y^4+x^4+12*x*y^3+2*x^2*y^2+4*x^3*y
> b = x^2 + 4*x*y - y^2;
-y^2+x^2+4*x*y
> expand(a*b);
3*y^6+x^6-24*x*y^5+43*x^2*y^4+16*x^3*y^3+17*x^4*y^2+8*x^5*y
> collect(a*b,x);
3*y^6+48*x*y^4+2*x^2*y^2+x^4*(-y^2+x^2+4*x*y)+4*x^3*y*(-y^2+x^2+4*x*y)
> normal(a/b);
3*y^2+x^2
</screen>
</para>

<para>You can differentiate functions and expand them as Taylor or
Laurent series (the third argument of series is the evaluation point,
the fourth defines the order):
<screen>
> diff(tan(x),x);
tan(x)^2+1
> series(sin(x),x,0,4);
x-1/6*x^3+Order(x^4)
> series(1/tan(x),x,0,4);
x^(-1)-1/3*x+Order(x^2)
</screen>
</para>

<para>If you ever wanted to convert units in C or C++ and found this
is cumbersome, here is the solution.  Symbolic types can always be
used as tags for different types of objects.  Converting from wrong
units to the metric system is therefore easy:
<screen>
> in=.0254*m;
0.0254*m
> lb=.45359237*kg;
0.45359237*kg
> 200*lb/in^2;
140613.91592783185568*kg*m^(-2)
</screen>
</para>

</sect1>

</chapter>


<chapter>
<title>Installation</title>

<para>GiNaC's installation follows the spirit of most GNU software. It is
easily installed on your system by three steps: configuration, build,
installation.</para>

<sect1><title id="CLN-main">Prerequistes</title>

<para>In order to install GiNaC on your system, some prerequistes need
to be met.  First of all, you need to have a C++-compiler adhering to
the ANSI-standard <citation>ISO/IEC 14882:1998(E)</citation>.  We used
<literal>GCC</literal> for development so if you have a different
compiler you are on your own.  For the configuration to succeed you
need a Posix compliant shell installed in <literal>/bin/sh</literal>,
GNU <literal>bash</literal> is fine.  Perl is needed by the built
process as well, since some of the source files are automatically
generated by Perl scripts.  Last but not least, Bruno Haible's library
<literal>CLN</literal> is extensively used and needs to be installed
on your system.  Please get it from <ulink
url="ftp://ftp.santafe.edu/pub/gnu/"><literal>ftp://ftp.santafe.edu/pub/gnu/</literal></ulink>
or from <ulink
url="ftp://ftp.ilog.fr/pub/Users/haible/gnu/"><literal>ftp://ftp.ilog.fr/pub/Users/haible/gnu/</literal></ulink>
(it is covered by GPL) and install it prior to trying to install
GiNaC.  The configure script checks if it can find it and if it cannot
it will refuse to continue.</para></sect1>

<sect1><title>Configuration</title>

<para>To configure GiNaC means to prepare the source distribution for
building.  It is done via a shell script called
<literal>configure</literal> that is shipped with the sources.
(Actually, this script is by itself created with GNU Autoconf from the
files <literal>configure.in</literal> and
<literal>aclocal.m4</literal>.)  Since a configure script generated by
GNU Autoconf never prompts, all customization must be done either via
command line parameters or environment variables.  It accepts a list
of parameters, the complete set of which can be listed by calling it
with the <literal>--help</literal> option.  The most important ones
will be shortly described in what follows:
<itemizedlist>
  <listitem>
    <para><literal>--disable-shared</literal>: When given, this option
    switches off the build of a shared library, i.e. a 
    <literal>.so</literal>-file.  This may be convenient when developing
    because it considerably speeds up compilation.</para>
  </listitem>
  <listitem>
    <para><literal>--prefix=</literal><emphasis>PREFIX</emphasis>: The
    directory where the compiled library and headers are installed. It
    defaults to <literal>/usr/local</literal> which means that the
    library is installed in the directory
    <literal>/usr/local/lib</literal> and the header files in
    <literal>/usr/local/include/GiNaC</literal> and the documentation
    (like this one) into <literal>/usr/local/share/doc/GiNaC</literal>.</para>
  </listitem>
  <listitem>
    <para><literal>--libdir=</literal><emphasis>LIBDIR</emphasis>: Use
    this option in case you want to have the library installed in some
    other directory than
    <emphasis>PREFIX</emphasis><literal>/lib/</literal>.</para>
  </listitem>
  <listitem>
    <para><literal>--includedir=</literal><emphasis>INCLUDEDIR</emphasis>:
    Use this option in case you want to have the header files
    installed in some other directory than
    <emphasis>PREFIX</emphasis><literal>/include/ginac/</literal>. For
    instance, if you specify
    <literal>--includedir=/usr/include</literal> you will end up with
    the header files sitting in the directory
    <literal>/usr/include/ginac/</literal>. Note that the subdirectory
    <literal>GiNaC</literal> is enforced by this process in order to
    keep the header files separated from others.  This avoids some
    clashes and allows for an easier deinstallation of GiNaC. This ought
    to be considered A Good Thing (tm).</para>
  </listitem>
  <listitem>
    <para><literal>--datadir=</literal><emphasis>DATADIR</emphasis>:
    This option may be given in case you want to have the documentation 
    installed in some other directory than
    <emphasis>PREFIX</emphasis><literal>/share/doc/GiNaC/</literal>.
  </listitem>
</itemizedlist>
</para>

<para>In addition, you may specify some environment variables.
<literal>CXX</literal> holds the path and the name of the C++ compiler
in case you want to override the default in your path.  (The
<literal>configure</literal> script searches your path for
<literal>c++</literal>, <literal>g++</literal>,
<literal>gcc</literal>, <literal>CC</literal>, <literal>cxx</literal>
and <literal>cc++</literal> in that order.)  It may be very useful to
define some compiler flags with the <literal>CXXFLAGS</literal>
environment variable, like optimization, debugging information and
warning levels.  If ommitted, it defaults to <literal>-g
-O2</literal>.</para>

<para>The whole process is illustrated in the following two
examples. (Substitute <literal>setenv VARIABLE value</literal> for
<literal>export VARIABLE=value</literal> if the Berkeley C shell is
your login shell.)

<example><title>Sample sessions of how to call the
configure-script</title> <para>Simple configuration for a site-wide
GiNaC library assuming everything is in default paths:</para>
<screen>
<prompt>$</prompt> export CXXFLAGS="-Wall -O2"
<prompt>$</prompt> ./configure
</screen>
<para>Configuration for a private static GiNaC library with several
components sitting in custom places (site-wide <literal>GCC</literal>
and private <literal>CLN</literal>), the compiler pursueded to be
picky and full assertions switched on:</para>
<screen>
<prompt>$</prompt> export CXX=/usr/local/gnu/bin/c++
<prompt>$</prompt> export CPPFLAGS="${CPPFLAGS} -I${HOME}/include"
<prompt>$</prompt> export CXXFLAGS="${CXXFLAGS} -DDO_GINAC_ASSERT -ggdb -Wall -ansi -pedantic -O2"
<prompt>$</prompt> export LDFLAGS="${LDFLAGS} -L${HOME}/lib"
<prompt>$</prompt> ./configure --disable-shared --prefix=${HOME}
</screen>
</example>
</para>

</sect1>

<sect1><title>Building GiNaC</title>

<para>After proper configuration you should just build the whole
library by typing <literal>make</literal> at the command
prompt and go for a cup of coffee.</para>

<para>Just to make sure GiNaC works properly you may run a simple test
suite by typing <literal>make check</literal>.  This will compile some
sample programs, run them and compare the output to reference output.
Each of the checks should return a message <literal>passed</literal>
together with the CPU time used for that particular test.  If it does
not, something went wrong.  This is mostly intended to be a QA-check
if something was broken during the development, but not a sanity check
of your system.  Another intent is to allow people to fiddle around
with optimization.  If <literal>CLN</literal> was installed all right
this step is unlikely to return any errors.</para>

</sect1>

<sect1><title>Installation</title>

<para>To install GiNaC on your system, simply type <literal>make
install</literal>.  As described in the section about configuration
the files will be installed in the following directories (the
directories will be created if they don't already exist):
<itemizedlist>
  <listitem>
    <para><literal>libginac.a</literal> will go into
    <emphasis>PREFIX</emphasis><literal>/lib/</literal> (or
    <emphasis>LIBDIR</emphasis>) which defaults to
    <literal>/usr/local/lib/</literal>.  So will
    <literal>libginac.so</literal> if the the configure script was
    given the option <literal>--enable-shared</literal>.  In that
    case, the proper symlinks will be established as well (by running
    <literal>ldconfig</literal>).</para>
  </listitem>
  <listitem>
    <para>All the header files will be installed into
    <emphasis>PREFIX</emphasis><literal>/include/ginac/</literal> (or
    <emphasis>INCLUDEDIR</emphasis><literal>/ginac/</literal>, if
    specified).</para>
  </listitem>
  <listitem>
    <para>All documentation (HTML, Postscript and DVI) will be stuffed
    into
    <emphasis>PREFIX</emphasis><literal>/share/doc/GiNaC/</literal>
    (or <emphasis>DATADIR</emphasis><literal>/doc/GiNaC/</literal>, if
    specified).</para>
  </listitem>
</itemizedlist>
</para>

<para>Just for the record we will list some other useful make targets:
<literal>make clean</literal> deletes all files generated by
<literal>make</literal>, i.e. all the object files.  In addition
<literal>make distclean</literal> removes all files generated by
configuration.  And finally <literal>make uninstall</literal> removes
the installed library and header files<footnoteref
linkend="warnuninstall-1">.  

  <footnote id="warnuninstall-1"><para>Uninstallation does not work
  after you have called <literal>make distclean</literal> since the
  <literal>Makefile</literal> is itself generated by the configuration
  from <literal>Makefile.in</literal> and hence deleted by
  <literal>make distclean</literal>.  There are two obvious ways out
  of this dilemma.  First, you can run the configuration again with
  the same <emphasis>PREFIX</emphasis> thus creating a
  <literal>Makefile</literal> with a working
  <literal>uninstall</literal> target.  Second, you can do it by hand
  since you now know where all the files went during
  installation.</para></footnote>
</para>

</sect1>
</chapter>


<chapter>
<title>Basic Concepts</title>

<para>This chapter will describe the different fundamental objects
that can be handled with GiNaC.  But before doing so, it is worthwhile
introducing you to the more commonly used class of expressions,
representing a flexible meta-class for storing all mathematical
objects.</para>

<sect1><title>Expressions</title>

<para>The most common class of objects a user deals with is the
expression <literal>ex</literal>, representing a mathematical object
like a variable, number, function, sum, product, etc...  Expressions
may be put together to form new expressions, passed as arguments to
functions, and so on.  Here is a little collection of valid
expressions:
<example><title>Examples of expressions</title>
<programlisting>
    ex MyEx1 = 5;                       // simple number
    ex MyEx2 = x + 2*y;                 // polynomial in x and y
    ex MyEx3 = (x + 1)/(x - 1);         // rational expression
    ex MyEx4 = sin(x + 2*y) + 3*z + 41; // containing a function
    ex MyEx5 = MyEx4 + 1;               // similar to above
</programlisting>
</example>
Before describing the more fundamental objects that form the building
blocks of expressions we'll have a quick look under the hood by
describing how expressions are internally managed.</para>

<sect2><title>Digression: Expressions are reference counted</title>

<para>An expression is extremely light-weight since internally it
works like a handle to the actual representation and really holds
nothing more than a pointer to some other object. What this means in
practice is that whenever you create two <literal>ex</literal> and set
the second equal to the first no copying process is involved. Instead,
the copying takes place as soon as you try to change the second.
Consider the simple sequence of code:
<example><title>Simple copy-on-write semantics</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol x("x"), y("y"), z("z");
    ex e1, e2;

    e1 = sin(x + 2*y) + 3*z + 41;
    e2 = e1;                // e2 points to same object as e1
    cout &lt;&lt; e2 &lt;&lt; endl;     // prints sin(x+2*y)+3*z+41
    e2 += 1;                // e2 is copied into a new object
    cout &lt;&lt; e2 &lt;&lt; endl;     // prints sin(x+2*y)+3*z+42
    // ...
}
</programlisting>
</example>
The line <literal>e2 = e1;</literal> creates a second expression
pointing to the object held already by <literal>e1</literal>.  The
time involved for this operation is therefore constant, no matter how
large <literal>e1</literal> was.  Actual copying, however, must take
place in the line <literal>e2 += 1</literal> because
<literal>e1</literal> and <literal>e2</literal> are not handles for
the same object any more.  This concept is called
<emphasis>copy-on-write semantics</emphasis>.  It increases
performance considerably whenever one object occurs multiple times and
represents a simple garbage collection scheme because when an
<literal>ex</literal> runs out of scope its destructor checks whether
other expressions handle the object it points to too and deletes the
object from memory if that turns out not to be the case.  A slightly
less trivial example of differentiation using the chain-rule should
make clear how powerful this can be.  <example><title>Advanced
copy-on-write semantics</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol x("x"), y("y");

    ex e1 = x + 3*y;
    ex e2 = pow(e1, 3);
    ex e3 = diff(sin(e2), x);   // first derivative of sin(e2) by x
    cout &lt;&lt; e1 &lt;&lt; endl          // prints x+3*y
         &lt;&lt; e2 &lt;&lt; endl          // prints (x+3*y)^3
         &lt;&lt; e3 &lt;&lt; endl;         // prints 3*(x+3*y)^2*cos((x+3*y)^3)
    // ...
}
</programlisting>
</example>
Here, <literal>e1</literal> will actually be referenced three times
while <literal>e2</literal> will be referenced two times.  When the
power of an expression is built, that expression needs not be
copied.  Likewise, since the derivative of a power of an expression can
be easily expressed in terms of that expression, no copying of
<literal>e1</literal> is involved when <literal>e3</literal> is
constructed.  So, when <literal>e3</literal> is constructed it will
print as <literal>3*(x+3*y)^2*cos((x+3*y)^3)</literal> but the
argument of <literal>cos()</literal> only holds a reference to
<literal>e2</literal> and the factor in front is just
<literal>3*e1^2</literal>.
</para>

<para>As a user of GiNaC, you cannot see this mechanism of
copy-on-write semantics.  When you insert an expression into a second
expression, the result behaves exactly as if the contents of the first
expression were inserted.  But it may be useful to remember that this
is not what happens.  Knowing this will enable you to write much more
efficient code.  If you still have an uncertain feeling with
copy-on-write semantics, we recommend you have a look at the
<emphasis>C++-FAQ lite</emphasis> by Marshall Cline.  Chapter 16
covers this issue and presents an implementation which is pretty close
to the one in GiNaC.  You can find it on the Web at <ulink
url="http://www.cerfnet.com/~mpcline/c++-faq-lite/"><literal>http://www.cerfnet.com/~mpcline/c++-faq-lite/</literal></ulink>.</para>

<para>So much for expressions.  But what exactly are these expressions
handles of?  This will be answered in the following sections.</para>
</sect2>
</sect1>

<sect1><title>The Class Hierarchy</title>

<para>GiNaC's class hierarchy consists of several classes representing
mathematical objects, all of which (except for <literal>ex</literal>
and some helpers) are internally derived from one abstract base class
called <literal>basic</literal>.  You do not have to deal with objects
of class <literal>basic</literal>, instead you'll be dealing with
symbols and functions of symbols.  You'll soon learn in this chapter
how many of the functions on symbols are really classes.  This is
because simple symbolic arithmetic is not supported by languages like
C++ so in a certain way GiNaC has to implement its own arithmetic.</para>

<para>To give an idea about what kinds of symbolic composits may be
built we have a look at the most important classes in the class
hierarchy.  The dashed line symbolizes a "points to" or "handles"
relationship while the solid lines stand for "inherits from"
relationships.
<figure id="classhier-id" float="1">
<title>The GiNaC class hierarchy</title>
  <graphic align="center" fileref="classhierarchy.graext" format="GRAEXT"></graphic>
</figure>
Some of the classes shown here (the ones sitting in white boxes) are
abstract base classes that are of no interest at all for the user.
They are used internally in order to avoid code duplication if
two or more classes derived from them share certain features.  An
example would be <literal>expairseq</literal>, which is a container
for a sequence of pairs each consisting of one expression and a number
(<literal>numeric</literal>).  What <emphasis>is</emphasis> visible to
the user are the derived classes <literal>add</literal> and
<literal>mul</literal>, representing sums of terms and products,
respectively.  We'll come back later to some more details about these
two classes and motivate the use of pairs in sums and products here.</para>

<sect2><title>Digression: Internal representation of products and sums</title>

<para>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 symbolic
expression
<emphasis>2*d<superscript>3</superscript>*(4*a+5*b-3)</emphasis>,
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:
<figure id="repres-naive-id" float="1">
<title>Naive internal representation-tree for <emphasis>2*d<superscript>3</superscript>*(4*a+5*b-3)</emphasis></title>
  <graphic align="center" fileref="rep_naive.graext" format="GRAEXT"></graphic>
</figure>
However, doing so results in a rather deeply nested tree which will
quickly become inefficient to manipulate.  If we represent the sum
instead as a sequence of terms, each having a purely numeric
multiplicative coefficient and the multiplication as a sequence of
terms, each having a numeric exponent, the tree becomes much more
flat.
<figure id="repres-pair-id" float="1">
<title>Pair-wise internal representation-tree for <emphasis>2*d<superscript>3</superscript>*(4*a+5*b-3)</emphasis></title>
  <graphic align="center" fileref="rep_pair.graext" format="GRAEXT"></graphic>
</figure>
The number <literal>3</literal> above the symbol <literal>d</literal>
shows that <literal>mul</literal> objects are treated similarly where
the coefficients are interpreted as <emphasis>exponents</emphasis>
now.  Addition of sums of terms or multiplication of products with
numerical exponents can be coded to be very efficient with such a
pair-representation.  Internally, this handling is done by many CAS in
this way.  It typically speeds up manipulations by an order of
magnitude.  The overall multiplicative factor <literal>2</literal> and
the additive term <literal>-3</literal> look somewhat cumbersome in
this representation, however, since they are still carrying a trivial
exponent and multiplicative factor <literal>1</literal> respectively.
Within GiNaC, this is avoided by adding a field that carries overall
numeric coefficient.
<figure id="repres-real-id" float="1">
<title>Realistic picture of GiNaC's representation-tree for <emphasis>2*d<superscript>3</superscript>*(4*a+5*b-3)</emphasis></title>
  <graphic align="center" fileref="rep_real.graext" format="GRAEXT"></graphic>
</figure>
This also allows for a better handling of numeric radicals, since
<literal>sqrt(2)</literal> can now be carried along calculations.  Now
it should be clear, why both classes <literal>add</literal> and
<literal>mul</literal> 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 such are
reimplemented for <literal>add</literal> and <literal>mul</literal>,
but the data structure is inherited from
<literal>expairseq</literal>.</para>

</sect1>

<sect1><title>Symbols</title>

<para>Symbols are for symbolic manipulation what atoms are for
chemistry.  You can declare objects of class <literal>symbol</literal>
as any other object simply by saying <literal>symbol x,y;</literal>.
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
<literal>symbol x("x");</literal>.  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.</para>

<para>This implies that the stings passed to symbols at construction
time may not be used for comparing two of them.  It is perfectly
legitimate to write <literal>symbol x("x"),y("x");</literal> but it is
likely to lead into trouble.  Here, <literal>x</literal> and
<literal>y</literal> are different symbols and statements like
<literal>x-y</literal> will not be simplified to zero although the
output <literal>x-x</literal> 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 <literal>operator==</literal> for instance) will always reveal
their difference.  Watch out, please.</para>

<para>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 <literal>.subs()</literal>
method.</para>

</sect1>

<sect1><title>Numbers</title>

<para>For storing numerical things, GiNaC uses Bruno Haible's library
<literal>CLN</literal>.  The classes therein serve as foundation
classes for GiNaC.  <literal>CLN</literal> stands for Class Library
for Numbers or alternatively for Common Lisp Numbers.  In order to
find out more about <literal>CLN</literal>'s internals the reader is
refered to the documentation of that library.  Suffice to say that it
is by itself build on top of another library, the GNU Multiple
Precision library <literal>GMP</literal>, which is an extremely fast
library for arbitrary long integers and rationals as well as arbitrary
precision floating point numbers.  It is very commonly used by several
popular cryptographic applications.  <literal>CLN</literal> extends
<literal>GMP</literal> by several useful things: First, it introduces
the complex number field over either reals (i.e. floating point
numbers with arbitrary precision) or rationals.  Second, it
automatically converts rationals to integers if the denominator is
unity and complex numbers to real numbers if the imaginary part
vanishes and also correctly treats algebraic functions.  Third it
provides good implementations of state-of-the-art algorithms for all
trigonometric and hyperbolic functions as well as for calculation of
some useful constants.</para>

<para>The user can construct an object of class
<literal>numeric</literal> in several ways.  The following example
shows the four most important constructors: construction from
C-integer, construction of fractions from two integers, construction
from C-float and construction from a string.
<example><title>Construction of numbers</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    numeric two(2);                     // exact integer 2
    numeric r(2,3);                     // exact fraction 2/3
    numeric e(2.71828);                 // floating point number
    numeric p("3.1415926535897932385"); // floating point number

    cout &lt;&lt; two*p &lt;&lt; endl;  // floating point 6.283...
    // ...
}
</programlisting>
</example>
Note that all those constructors are <emphasis>explicit</emphasis>
which means you are not allowed to write <literal>numeric
two=2;</literal>.  This is because the basic objects to be handled by
GiNaC are the expressions <literal>ex</literal> and we want to keep
things simple and wish objects like <literal>pow(x,2)</literal> to be
handled the same way as <literal>pow(x,a)</literal>, which means that
we need to allow a general <literal>ex</literal> as base and exponent.
Therefore there is an implicit constructor from C-integers directly to
expressions handling numerics at work in most of our examples.  This
design really becomes convenient when one declares own functions
having more than one parameter but it forbids using implicit
constructors because that would lead to ambiguities. </para>

<para>It may be tempting to construct numbers writing <literal>numeric
r(3/2)</literal>.  This would, however, call C's built-in operator
<literal>/</literal> for integers first and result in a numeric
holding a plain integer 1.  <emphasis>Never use
</emphasis><literal>/</literal><emphasis> on integers!</emphasis> Use
the constructor from two integers instead, as shown in the example
above.  Writing <literal>numeric(1)/2</literal> may look funny but
works also. </para>

<para>We have seen now the distinction between exact numbers and
floating point numbers.  Clearly, the user should never have to worry
about dynamically created exact numbers, since their "exactness"
always determines how they ought to be handled.  The situation is
different for floating point numbers.  Their accuracy is handled by
one <emphasis>global</emphasis> variable, called
<literal>Digits</literal>.  (For those readers who know about Maple:
it behaves very much like Maple's <literal>Digits</literal>).  All
objects of class numeric that are constructed from then on will be
stored with a precision matching that number of decimal digits:
<example><title>Controlling the precision of floating point numbers</title>
<programlisting> 
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

void foo()
{
    numeric three(3.0), one(1.0);
    numeric x = one/three;

    cout &lt;&lt; "in " &lt;&lt; Digits &lt;&lt; " digits:" &lt;&lt; endl;
    cout &lt;&lt; x &lt;&lt; endl;
    cout &lt;&lt; Pi.evalf() &lt;&lt; endl;
}

int main()
{
    foo();
    Digits = 60;
    foo();
    return 0;
}
</programlisting>
</example>
The above example prints the following output to screen:
<screen>
in 17 digits:
0.333333333333333333
3.14159265358979324
in 60 digits:
0.333333333333333333333333333333333333333333333333333333333333333333
3.14159265358979323846264338327950288419716939937510582097494459231
</screen>
</para>

<para>It should be clear that objects of class
<literal>numeric</literal> should be used for constructing numbers or
for doing arithmetic with them.  The objects one deals with most of
the time are the polymorphic expressions <literal>ex</literal>.</para>

<sect2><title>Tests on numbers</title>

<para>Once you have declared some numbers, assigned them to
expressions and done some arithmetic with them it is frequently
desired to retrieve some kind of information from them like asking
whether that number is integer, rational, real or complex.  For those
cases GiNaC provides several useful methods.  (Internally, they fall
back to invocations of certain CLN functions.)</para>

<para>As an example, let's construct some rational number, multiply it
with some multiple of its denominator and check what comes out:
<example><title>Sample test on objects of type numeric</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

// some very important constants:
const numeric twentyone(21);
const numeric ten(10);
const numeric fife(5);

int main()
{
    numeric answer = twentyone;

    answer /= five;
    cout &lt;&lt; answer.is_integer() &lt;&lt; endl;  // false, it's 21/5
    answer *= ten;
    cout &lt;&lt; answer.is_integer() &lt;&lt; endl;  // true, it's 42 now!
    // ...
}
</programlisting>
</example>

Note that the variable <literal>answer</literal> is constructed here
as an integer by <literal>numeric</literal>'s copy constructor but in
an intermediate step it holds a rational number represented as integer
numerator and integer denominator.  When multiplied by 10, the
denominator becomes unity and the result is automatically converted to
a pure integer again.  Internally, the underlying
<literal>CLN</literal> is responsible for this behaviour and we refer
the reader to <literal>CLN</literal>'s documentation.  Suffice to say
that the same behaviour applies to complex numbers as well as return
values of certain functions.  Complex numbers are automatically
converted to real numbers if the imaginary part becomes zero.  The
full set of tests that can be applied is listed in the following
table.

<informaltable colsep="0" frame="topbot" pgwide="1">
<tgroup cols="2">
<colspec colnum="1" colwidth="1*">
<colspec colnum="2" colwidth="2*">
<thead>
  <row>
    <entry>Method</entry>
    <entry>Returns true if...</entry>
  </row>
</thead>
<tbody>
  <row>
    <entry><literal>.is_zero()</literal></entry>
    <entry>object is equal to zero</entry>
  </row>
  <row>
    <entry><literal>.is_positive()</literal></entry>
    <entry>object is not complex and greater than 0</entry>
  </row>
  <row>
    <entry><literal>.is_integer()</literal></entry>
    <entry>object is a (non-complex) integer</entry>
  </row>
  <row>
    <entry><literal>.is_pos_integer()</literal></entry>
    <entry>object is an integer and greater than 0</entry>
  </row>
  <row>
    <entry><literal>.is_nonneg_integer()</literal></entry>
    <entry>object is an integer and greater equal 0</entry>
  </row>
  <row>
    <entry><literal>.is_even()</literal></entry>
    <entry>object is an even integer</entry>
  </row>
  <row>
    <entry><literal>.is_odd()</literal></entry>
    <entry>object is an odd integer</entry>
  </row>
  <row>
    <entry><literal>.is_prime()</literal></entry>
    <entry>object is a prime integer (probabilistic primality test)</entry>
  </row>
  <row>
    <entry><literal>.is_rational()</literal></entry>
    <entry>object is an exact rational number (integers are rational, too, as are complex extensions like <literal>2/3+7/2*I</literal>)</entry>
  </row>
  <row>
    <entry><literal>.is_real()</literal></entry>
    <entry>object is a real integer, rational or float (i.e. is not complex)</entry>
  </row>
</tbody>
</tgroup>
</informaltable>
</para>

</sect2>

</sect1>


<sect1><title>Constants</title>

<para>Constants behave pretty much like symbols except that that they return
some specific number when the method <literal>.evalf()</literal> is called.
</para>

<para>The predefined known constants are:
<informaltable colsep="0" frame="topbot" pgwide="1">
<tgroup cols="3">
<colspec colnum="1" colwidth="1*">
<colspec colnum="2" colwidth="2*">
<colspec colnum="3" colwidth="4*">
<thead>
  <row>
    <entry>Name</entry>
    <entry>Common Name</entry>
    <entry>Numerical Value (35 digits)</entry>
  </row>
</thead>
<tbody>
  <row>
    <entry><literal>Pi</literal></entry>
    <entry>Archimedes' constant</entry>
    <entry>3.14159265358979323846264338327950288</entry>
  </row><row>
    <entry><literal>Catalan</literal></entry>
    <entry>Catalan's constant</entry>
    <entry>0.91596559417721901505460351493238411</entry>
  </row><row>
    <entry><literal>EulerGamma</literal></entry>
    <entry>Euler's (or Euler-Mascheroni) constant</entry>
    <entry>0.57721566490153286060651209008240243</entry>
  </row>
</tbody>
</tgroup>
</informaltable>
</para>

</sect1>

<sect1><title>Fundamental operations: The <literal>power</literal>, <literal>add</literal> and <literal>mul</literal> classes</title>

<para>Simple polynomial expressions are written down in GiNaC pretty
much like in other CAS.  The necessary operators <literal>+</literal>,
<literal>-</literal>, <literal>*</literal> and <literal>/</literal>
have been overloaded to achieve this goal.  When you run the following
program, the constructor for an object of type <literal>mul</literal>
is automatically called to hold the product of <literal>a</literal>
and <literal>b</literal> and then the constructor for an object of
type <literal>add</literal> is called to hold the sum of that
<literal>mul</literal> object and the number one:
<example><title>Construction of <literal>add</literal> and <literal>mul</literal> objects</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol a("a"), b("b");
    ex MyTerm = 1+a*b;
    // ...
}
</programlisting>
</example></para>

<para>For exponentiation, you have already seen the somewhat clumsy
(though C-ish) statement <literal>pow(x,2);</literal> to represent
<literal>x</literal> squared.  This direct construction is necessary
since we cannot safely overload the constructor <literal>^</literal>
in <literal>C++</literal> to construct a <literal>power</literal>
object.  If we did, it would have several counterintuitive effects:
<itemizedlist>
  <listitem>
    <para>Due to <literal>C</literal>'s operator precedence,
    <literal>2*x^2</literal> would be parsed as <literal>(2*x)^2</literal>.
  </listitem>
  <listitem>
    <para>Due to the binding of the operator <literal>^</literal>, 
    <literal>x^a^b</literal> would result in <literal>(x^a)^b</literal>. 
    This would be confusing since most (though not all) other CAS 
    interpret this as <literal>x^(a^b)</literal>.
  </listitem>
  <listitem>
    <para>Also, expressions involving integer exponents are very 
    frequently used, which makes it even more dangerous to overload 
    <literal>^</literal> since it is then hard to distinguish between the
    semantics as exponentiation and the one for exclusive or.  (It would
    be embarassing to return <literal>1</literal> where one has requested 
    <literal>2^3</literal>.)</para>
  </listitem>
</itemizedlist>
All effects are contrary to mathematical notation and differ from the
way most other CAS handle exponentiation, therefore overloading
<literal>^</literal> is ruled out for GiNaC's C++ part.  The situation
is different in <literal>ginsh</literal>, there the
exponentiation-<literal>^</literal> exists.  (Also note, that the
other frequently used exponentiation operator <literal>**</literal>
does not exist at all in <literal>C++</literal>).</para>

<para>To be somewhat more precise, objects of the three classes
described here, are all containers for other expressions.  An object
of class <literal>power</literal> is best viewed as a container with
two slots, one for the basis, one for the exponent.  All valid GiNaC
expressions can be inserted.  However, basic transformations like
simplifying <literal>pow(pow(x,2),3)</literal> to
<literal>x^6</literal> automatically are only performed when
this is mathematically possible.  If we replace the outer exponent
three in the example by some symbols <literal>a</literal>, the
simplification is not safe and will not be performed, since
<literal>a</literal> might be <literal>1/2</literal> and
<literal>x</literal> negative.</para>

<para>Objects of type <literal>add</literal> and
<literal>mul</literal> are containers with an arbitrary number of
slots for expressions to be inserted.  Again, simple and safe
simplifications are carried out like transforming
<literal>3*x+4-x</literal> to <literal>2*x+4</literal>.</para>

<para>The general rule is that when you construct such objects, GiNaC
automatically creates them in canonical form, which might differ from
the form you typed in your program.  This allows for rapid comparison
of expressions, since after all <literal>a-a</literal> is simply zero.
Note, that the canonical form is not necessarily lexicographical
ordering or in any way easily guessable.  It is only guaranteed that
constructing the same expression twice, either implicitly or
explicitly, results in the same canonical form.</para>

</sect1>

<sect1><title>Built-in Functions</title>

<para>There are quite a number of useful functions built into GiNaC.
They are all objects of class <literal>function</literal>.  They
accept one or more expressions as arguments and return one expression.
If the arguments are not numerical, the evaluation of the functions
may be halted, as it does in the next example:
<example><title>Evaluation of built-in functions</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol x("x"), y("y");
    
    ex foo = x+y/2;
    cout &lt;&lt; "gamma(" &lt;&lt; foo &lt;&lt; ") -> " &lt;&lt; gamma(foo) &lt;&lt; endl;
    ex bar = foo.subs(y==1);
    cout &lt;&lt; "gamma(" &lt;&lt; bar &lt;&lt; ") -> " &lt;&lt; gamma(bar) &lt;&lt; endl;
    ex foobar= bar.subs(x==7);
    cout &lt;&lt; "gamma(" &lt;&lt; foobar &lt;&lt; ") -> " &lt;&lt; gamma(foobar) &lt;&lt; endl;
    // ...
}
</programlisting>
<para>This program will type out two times a function and then an
expression that may be really useful:
<screen>
gamma(x+(1/2)*y) -> gamma(x+(1/2)*y)
gamma(x+1/2) -> gamma(x+1/2)
gamma(15/2) -> (135135/128)*Pi^(1/2)
</screen></para>
</example>
Most of these functions can be differentiated, series expanded so on.
Read the next chapter in order to learn more about this..</para>

</sect1>

</chapter>


<chapter>
<title>Important Algorithms</title>

<para>In this chapter the most important algorithms provided by GiNaC
will be described.  Some of them are implemented as functions on
expressions, others are implemented as methods provided by expression
objects.  If they are methods, there exists a wrapper function around
it, so you can alternatively call it in a functional way as shown in
the simple example:
<example><title>Methods vs. wrapper functions</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    ex x = numeric(1.0);
    
    cout &lt;&lt; "As method:   " &lt;&lt; sin(x).evalf() &lt;&lt; endl;
    cout &lt;&lt; "As function: " &lt;&lt; evalf(sin(x)) &lt;&lt; endl;
    // ...
}
</programlisting>
</example>
The general rule is that wherever methods accept one or more
parameters (<emphasis>arg1</emphasis>, <emphasis>arg2</emphasis>, ...)
the order of arguments the function wrapper accepts is the same but
preceded by the object to act on (<emphasis>object</emphasis>,
<emphasis>arg1</emphasis>, <emphasis>arg2</emphasis>, ...).  This
approach is the most natural one in an OO model but it may lead to
confusion for MapleV users because where they would type
<literal>A:=x+1; subs(x=2,A);</literal> GiNaC would require
<literal>A=x+1; subs(A,x==2);</literal> (after proper declaration of A
and x).  On the other hand, since MapleV returns 3 on
<literal>A:=x^2+3; coeff(A,x,0);</literal> (GiNaC:
<literal>A=pow(x,2)+3; coeff(A,x,0);</literal>) it is clear that
MapleV is not trying to be consistent here.  Also, users of MuPAD will
in most cases feel more comfortable with GiNaC's convention.  All
function wrappers are always implemented as simple inline functions
which just call the corresponding method and are only provided for
users uncomfortable with OO who are dead set to avoid method
invocations.  Generally, a chain of function wrappers is much harder
to read than a chain of methods and should therefore be avoided if
possible.  On the other hand, not everything in GiNaC is a method on
class <literal>ex</literal> and sometimes calling a function cannot be
avoided.
</para>

<sect1><title>Polynomial Expansion</title>

<para>A polynomial in one or more variables has many equivalent
representations.  Some useful ones serve a specific purpose.  Consider
for example the trivariate polynomial <literal>4*x*y + x*z + 20*y^2 +
21*y*z + 4*z^2</literal>.  It is equivalent to the factorized
polynomial <literal>(x + 5*y + 4*z)*(4*y + z)</literal>.  Other
representations are the recursive ones where one collects for
exponents in one of the three variable.  Since the factors are
themselves polynomials in the remaining two variables the procedure
can be repeated.  In our expample, two possibilies would be
<literal>(4*y + z)*x + 20*y^2 + 21*y*z + 4*z^2</literal> and
<literal>20*y^2 + (21*z + 4*x)*y + 4*z^2 + x*z</literal>.
</para>

<para>To bring an expression into expanded form, its method
<function>.expand()</function> may be called.  In our example above,
this corresponds to <literal>4*x*y + x*z + 20*y^2 + 21*y*z +
4*z^2</literal>.  Again, since the canonical form in GiNaC is not
easily guessable you should be prepared to see different orderings of
terms in such sums!</para>

</sect1>

<sect1><title>Collecting expressions</title>

<para>Another useful representation of multivariate polynomials is as
a univariate polynomial in one of the variables with the coefficients
being polynomials in the remaining variables.  The method
<literal>collect()</literal> accomplishes this task:
<funcsynopsis>
  <funcsynopsisinfo>#include &lt;ginac/ginac.h></funcsynopsisinfo>
  <funcdef>ex <function>ex::collect</function></funcdef>
  <paramdef>symbol const & <parameter>s</parameter></paramdef>
</funcsynopsis>
Note that the original polynomial needs to be in expanded form in
order to be able to find the coefficients properly.  The range of
occuring coefficients can be checked using the two methods
<funcsynopsis>
  <funcsynopsisinfo>#include &lt;ginac/ginac.h></funcsynopsisinfo>
  <funcdef>int <function>ex::degree</function></funcdef>
  <paramdef>symbol const & <parameter>s</parameter></paramdef>
</funcsynopsis>
<funcsynopsis>
  <funcdef>int <function>ex::ldegree</function></funcdef>
  <paramdef>symbol const & <parameter>s</parameter></paramdef>
</funcsynopsis>
where <literal>degree()</literal> returns the highest coefficient and
<literal>ldegree()</literal> the lowest one.  These two methods work
also reliably on non-expanded input polynomials.  This is illustrated
in the following example: 

<example><title>Collecting expressions in multivariate polynomials</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol x("x"), y("y");
    ex PolyInp = 4*pow(x,3)*y + 5*x*pow(y,2) + 3*y
                 - pow(x+y,2) + 2*pow(y+2,2) - 8;
    ex Poly = PolyInp.expand();
    
    for (int i=Poly.ldegree(x); i<=Poly.degree(x); ++i) {
        cout &lt;&lt; "The x^" &lt;&lt; i &lt;&lt; "-coefficient is "
             &lt;&lt; Poly.coeff(x,i) &lt;&lt; endl;
    }
    cout &lt;&lt; "As polynomial in y: " 
         &lt;&lt; Poly.collect(y) &lt;&lt; endl;
    // ...
}
</programlisting>
</example>
When run, it returns an output in the following fashion:
<screen>
The x^0-coefficient is y^2+11*y
The x^1-coefficient is 5*y^2-2*y
The x^2-coefficient is -1
The x^3-coefficient is 4*y
As polynomial in y: -x^2+(5*x+1)*y^2+(-2*x+4*x^3+11)*y
</screen>
As always, the exact output may vary between different versions of
GiNaC or even from run to run since the internal canonical ordering is
not within the user's sphere of influence.</para>

</sect1>

<sect1><title>Polynomial Arithmetic</title>

<sect2><title>GCD and LCM</title>

<para>The functions for polynomial greatest common divisor and least common
multiple have the synopsis:
<funcsynopsis>
  <funcsynopsisinfo>#include &lt;GiNaC/normal.h></funcsynopsisinfo>
  <funcdef>ex <function>gcd</function></funcdef>
  <paramdef>const ex *<parameter>a</parameter>, const ex *<parameter>b</parameter></paramdef>
</funcsynopsis>
<funcsynopsis>
  <funcdef>ex <function>lcm</function></funcdef>
  <paramdef>const ex *<parameter>a</parameter>, const ex *<parameter>b</parameter></paramdef>
</funcsynopsis></para>

<para>The functions <function>gcd()</function> and <function
id="lcm-main">lcm()</function> accepts two expressions
<literal>a</literal> and <literal>b</literal> as arguments and return
a new expression, their greatest common divisor or least common
multiple, respectively.  If the polynomials <literal>a</literal> and
<literal>b</literal> are coprime <function>gcd(a,b)</function> returns 1
and <function>lcm(a,b)</function> returns the product of
<literal>a</literal> and <literal>b</literal>.
<example><title>Polynomal GCD/LCM</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol x("x"), y("y"), z("z");
    ex P_a = 4*x*y + x*z + 20*pow(y, 2) + 21*y*z + 4*pow(z, 2);
    ex P_b = x*y + 3*x*z + 5*pow(y, 2) + 19*y*z + 12*pow(z, 2);

    ex P_gcd = gcd(P_a, P_b);
    // x + 5*y + 4*z
    ex P_lcm = lcm(P_a, P_b);
    // 4*x*y^2 + 13*y*x*z + 20*y^3 + 81*y^2*z + 67*y*z^2 + 3*x*z^2 + 12*z^3
    // ...
}
</programlisting>
</example>
</para>

</sect2>

<sect2><title>The <function>normal</function> method</title>

<para>While in common symbolic code <function>gcd()</function> and
<function>lcm()</function> are not too heavily used, simplification
occurs frequently.  Therefore <function>.normal()</function>, which
provides some basic form of simplification, has become a method of
class <literal>ex</literal>, just like <literal>.expand()</literal>.
It converts a rational function into an equivalent rational function
where numererator and denominator are coprime.  This means, it finds
the GCD of numerator and denominator and cancels it.  If it encounters
some object which does not belong to the domain of rationals (a
function for instance), that object is replaced by a temporary symbol.
This means that both expressions <literal>t1</literal> and
<literal>t2</literal> are indeed simplified in this little program:
<example><title>Cancellation of polynomial GCD (with obstacles)</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol x("x");
    ex t1 = (pow(x,2) + 2*x + 1)/(x + 1);
    ex t2 = (pow(sin(x),2) + 2*sin(x) + 1)/(sin(x) + 1);
    cout &lt;&lt; "t1 is " &lt;&lt; t1.normal() &lt;&lt; endl;
    cout &lt;&lt; "t2 is " &lt;&lt; t2.normal() &lt;&lt; endl;
    // ...
}
</programlisting>
</example>

Of course this works for multivariate polynomials too, so the ratio of
the sample-polynomials from the section about GCD and LCM above would
be normalized to <literal>P_a/P_b</literal> =
<literal>(4*y+z)/(y+3*z)</literal>.</para>

</sect2>

</sect1>

<sect1><title>Symbolic Differentiation</title>

<para>GiNaC's objects know how to differentiate themselves.  Thus, a
polynomial (class <literal>add</literal>) knows that its derivative is
the sum of the derivatives of all the monomials:
<example><title>Simple polynomial differentiation</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol x("x"), y("y"), z("z");
    ex P = pow(x, 5) + pow(x, 2) + y;

    cout &lt;&lt; P.diff(x,2) &lt;&lt; endl;  // 20*x^3 + 2
    cout &lt;&lt; P.diff(y) &lt;&lt; endl;    // 1
    cout &lt;&lt; P.diff(z) &lt;&lt; endl;    // 0
    // ...
}
</programlisting>
</example>
If a second integer parameter <emphasis>n</emphasis> is given the
<function>diff</function> method returns the <emphasis>n</emphasis>th
derivative.</para>

<para>If <emphasis>every</emphasis> object and every function is told
what its derivative is, all derivatives of composed objects can be
calculated using the chain rule and the product rule.  Consider, for
instance the expression <literal>1/cosh(x)</literal>.  Since the
derivative of <literal>cosh(x)</literal> is <literal>sinh(x)</literal>
and the derivative of <literal>pow(x,-1)</literal> is
<literal>-pow(x,-2)</literal>, GiNaC can readily compute the
composition.  It turns out that the composition is the generating
function for Euler Numbers, i.e. the so called
<emphasis>n</emphasis>th Euler number is the coefficient of
<literal>x^n/n!</literal> in the expansion of
<literal>1/cosh(x)</literal>.  We may use this identity to code a
function that generates Euler numbers in just three lines:
<example><title>Differentiation with nontrivial functions: Euler numbers</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

ex EulerNumber(unsigned n)
{
    symbol x;
    ex generator = pow(cosh(x),-1);
    return generator.diff(x,n).subs(x==0);
}

int main()
{
    for (unsigned i=0; i&lt;11; i+=2)
        cout &lt;&lt; EulerNumber(i) &lt;&lt; endl;
    return 0;
}
</programlisting>
</example>
When you run it, it produces the sequence <literal>1</literal>,
<literal>-1</literal>, <literal>5</literal>, <literal>-61</literal>,
<literal>1385</literal>, <literal>-50521</literal>.  We increment the
loop variable <literal>i</literal> by two since all odd Euler numbers
vanish anyways.</para>

</sect1>

<sect1><title>Series Expansion</title>

<para>Expressions know how to expand themselves as a Taylor series or
(more generally) a Laurent series.  As in most conventional Computer
Algebra Systems no distinction is made between those two.  There is a
class of its own for storing such series as well as a class for
storing the order of the series.  A sample program could read:
<example><title>Series expansion</title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

int main()
{
    symbol x("x");
    numeric point(0);
    ex MyExpr1 = sin(x);
    ex MyExpr2 = 1/(x - pow(x, 2) - pow(x, 3));
    ex MyTailor, MySeries;
    
    MyTailor = MyExpr1.series(x, point, 5);
    cout &lt;&lt; MyExpr1 &lt;&lt; " == " &lt;&lt; MyTailor
         &lt;&lt; " for small " &lt;&lt; x &lt;&lt; endl;
    MySeries = MyExpr2.series(x, point, 7);
    cout &lt;&lt; MyExpr2 &lt;&lt; " == " &lt;&lt; MySeries
         &lt;&lt; " for small " &lt;&lt; x &lt;&lt; endl;
    // ...
}
</programlisting>
</example>
</para>

<para>As an instructive application, let us calculate the numerical
value of Archimedes' constant (for which there already exists the
built-in constant <literal>Pi</literal>) using M&eacute;chain's
mysterious formula <literal>Pi==16*atan(1/5)-4*atan(1/239)</literal>.
We may expand the arcus tangent around <literal>0</literal> and insert
the fractions <literal>1/5</literal> and <literal>1/239</literal>.
But, as we have seen, a series in GiNaC carries an order term with it.
The function <literal>series_to_poly</literal> may be used to strip 
this off:
<example><title>Series expansion using M&eacute;chain's formula for 
<literal>Pi</literal></title>
<programlisting>
#include &lt;ginac/ginac.h&gt;
using namespace GiNaC;

ex mechain_pi(int degr)
{
    symbol x;
    ex pi_expansion = series_to_poly(atan(x).series(x,0,degr));
    ex pi_approx = 16*pi_expansion.subs(x==numeric(1,5))
                   -4*pi_expansion.subs(x==numeric(1,239));
    return pi_approx;
}

int main()
{
    ex pi_frac;
    for (int i=2; i&lt;12; i+=2) {
        pi_frac = mechain_pi(i);
        cout &lt;&lt; i &lt;&lt; ":\t" &lt;&lt; pi_frac &lt;&lt; endl
             &lt;&lt; "\t" &lt;&lt; pi_frac.evalf() &lt;&lt; endl;
    }
    return 0;
}
</programlisting>
<para>When you run this program, it will type out:</para>
<screen>
2:      3804/1195
        3.1832635983263598326
4:      5359397032/1706489875
        3.1405970293260603143
6:      38279241713339684/12184551018734375
        3.141621029325034425
8:      76528487109180192540976/24359780855939418203125
        3.141591772182177295
10:     327853873402258685803048818236/104359128170408663038552734375
        3.1415926824043995174
</screen>
</example>
</para>

</sect1>

</chapter>


<chapter>
<title>Extending GiNaC</title>

<para>By reading so far you should have gotten a fairly good
understanding of GiNaC's design-patterns.  From here on you should
start reading the sources.  All we can do now is issue some
recommendations how to tackle GiNaC's many loose ends in order to
fulfill everybody's dreams.</para>

<sect1><title>What doesn't belong into GiNaC</title>

<para>First of all, GiNaC's name must be read literally.  It is
designed to be a library for use within C++.  The tiny
<literal>ginsh</literal> accompanying GiNaC makes this even more
clear: it doesn't even attempt to provide a language.  There are no
loops or conditional expressions in <literal>ginsh</literal>, it is
merely a window into the library for the programmer to test stuff (or
to show off).  Still, the design of a complete CAS with a language of
its own, graphical capabilites and all this on top of GiNaC is
possible and is without doubt a nice project for the future.</para>

<para>There are many built-in functions in GiNaC that do not know how
to evaluate themselves numerically to a precision declared at runtime
(using <literal>Digits</literal>).  Some may be evaluated at certain
points, but not generally.  This ought to be fixed.  However, doing
numerical computations with GiNaC's quite abstract classes is doomed
to be inefficient.  For this purpose, the underlying bignum-package
<literal>CLN</literal> is much better suited.</para>

</sect1>

<sect1><title>Other symbolic functions</title>

<para>The easiest and most instructive way to start with is probably
to implement your own function.  Objects of class
<literal>function</literal> are inserted into the system via a kind of
"registry".  They get a serial number that is used internally to
identify them but you usually need not worry about this.  What you
have to care for are functions that are called when the user invokes
certain methods.  These are usual C++-functions accepting a number of
<literal>ex</literal> as arguments and returning one
<literal>ex</literal>.  As an example, if we have a look at a
simplified implementation of the cosine trigonometric function, we
first need a function that is called when one wishes to
<literal>eval</literal> it.  It could look something like this:

<programlisting>
static ex cos_eval_method(ex const & x)
{
    // if x%2*Pi return 1
    // if x%Pi return -1
    // if x%Pi/2 return 0
    // care for other cases...
    return cos(x).hold();
}
</programlisting>
The last line returns <literal>cos(x)</literal> if we don't know what
else to do and stops a potential recursive evaluation by saying
<literal>.hold()</literal>.  We should also implement a method for
numerical evaluation and since we are lazy we sweep the problem under
the rug by calling someone else's function that does so, in this case
the one in class <literal>numeric</literal>:
<programlisting>
static ex cos_evalf_method(ex const & x)
{
    return sin(ex_to_numeric(x));
}
</programlisting>
Differentiation will surely turn up and so we need to tell
<literal>sin</literal> how to differentiate itself:
<programlisting>
static ex cos_diff_method(ex const & x, unsigned diff_param)
{
    return cos(x);
}
</programlisting>

The second parameter is obligatory but uninteresting at this point.
It is used for correct handling of the product rule only.  For Taylor
expansion, it is enough to know how to differentiate.  But if the
function you want to implement does have a pole somewhere in the
complex plane, you need to write another method for Laurent expansion
around that point.</para>

<para>Now that everything has been written for <literal>cos</literal>,
we need to tell the system about it.  This is done by a macro and we
are not going to descibe how it expands, please consult your
preprocessor if you are curious:
<programlisting>
REGISTER_FUNCTION(cos, cos_eval_method, cos_evalf_method, cos_diff, NULL);
</programlisting>
The first argument is the function's name, the second, third and
fourth bind the corresponding methods to this objects and the fifth is
a slot for inserting a method for series expansion.  Also, the new
function needs to be declared somewhere.  This may also be done by a
convenient preprocessor macro:
<programlisting>
DECLARE_FUNCTION_1P(cos)
</programlisting>
The suffix <literal>_1P</literal> stands for <emphasis>one
parameter</emphasis>.  Of course, this implementation of
<literal>cos</literal> is very incomplete and lacks several safety
mechanisms.  Please, have a look at the real implementation in GiNaC.
(By the way: in case you are worrying about all the macros above we
can assure you that functions are GiNaC's most macro-intense classes.
We have done our best to avoid them where we can.)</para>

<para>That's it. May the source be with you!</para>

</sect1>

</chapter>


<chapter>
<title>A Comparison with other CAS</title>

<para>This chapter will give you some information on how GiNaC
compares to other, traditional Computer Algebra Systems, like
<literal>Maple</literal>, <literal>Mathematica</literal> or
<literal>Reduce</literal>, where it has advantages and disadvantages
over these systems.</para>

<sect1><title>Advantages</title>

<para>GiNaC has several advantages over traditional Computer
Algebra Systems, like 

<itemizedlist>
  <listitem>
    <para>familiar language: all common CAS implement their own
    proprietary grammar which you have to learn first (and maybe learn
    again when your vendor chooses to "enhance" it).  With GiNaC you
    can write your program in common <literal>C++</literal>, which is
    standardized.</para>
  </listitem>
  <listitem>
    <para>structured data types: you can build up structured data
    types using <literal>struct</literal>s or <literal>class</literal>es
    together with STL features instead of using unnamed lists of lists
    of lists.</para>
  </listitem>
  <listitem>
    <para>strongly typed: in CAS, you usually have only one kind of
    variables which can hold contents of an arbitrary type.  This
    4GL like feature is nice for novice programmers, but dangerous.
    </para>
  </listitem>
  <listitem>
    <para>development tools: powerful development tools exist for
    <literal>C++</literal>, like fancy editors (e.g. with automatic
    indentation and syntax highlighting), debuggers, visualization
    tools, documentation tools...</para>
  </listitem>
  <listitem>
    <para>modularization: <literal>C++</literal> programs can 
    easily be split into modules by separating interface and
    implementation.</para>
  </listitem>
  <listitem>
    <para>price: GiNaC is distributed under the GNU Public License
    which means that it is free and available with source code.  And
    there are excellent <literal>C++</literal>-compilers for free, too.
    </para>
  </listitem>
  <listitem>
    <para>extendable: you can add your own classes to GiNaC, thus
    extending it on a very low level.  Compare this to a traditional
    CAS that you can usually only extend on a high level by writing in
    the language defined by the parser.  In particular, it turns out
    to be almost impossible to fix bugs in a traditional system.
  </listitem>
  <listitem>
    <para>seemless integration: it is somewhere between difficult
    and impossible to call CAS functions from within a program 
    written in <literal>C++</literal> or any other programming 
    language and vice versa.  With GiNaC, your symbolic routines
    are part of your program.  You can easily call third party
    libraries, e.g. for numerical evaluation or graphical 
    interaction.  All other approaches are much more cumbersome: they
    range from simply ignoring the problem
    (i.e. <literal>Maple</literal>) to providing a
    method for "embedding" the system
    (i.e. <literal>Yacas</literal>).</para>
  </listitem>
  <listitem>
    <para>efficiency: often large parts of a program do not need
    symbolic calculations at all.  Why use large integers for loop
    variables or arbitrary precision arithmetics where double
    accuracy is sufficient?  For pure symbolic applications,
    GiNaC is comparable in speed with other CAS.
  </listitem>
</itemizedlist>
</para>

<sect1><title>Disadvantages</title>

<para>Of course it also has some disadvantages

<itemizedlist>
  <listitem>
    <para>not interactive: GiNaC programs have to be written in 
    an editor, compiled and executed. You cannot play with 
    expressions interactively.  However, such an extension is not
    inherently forbidden by design.  In fact, two interactive
    interfaces are possible: First, a simple shell that exposes GiNaC's
    types to a command line can readily be written (and has been
    written) and second, as a more consistent approach we plan
    an integration with the <literal>CINT</literal>
    <literal>C++</literal> interpreter.</para>
  </listitem>
  <listitem>
    <para>advanced features: GiNaC cannot compete with a program
    like <literal>Reduce</literal> which exists for more than
    30 years now or <literal>Maple</literal> which grows since 
    1981 by the work of dozens of programmers, with respect to
    mathematical features. Integration, factorization, non-trivial
    simplifications, limits etc. are missing in GiNaC (and are not
    planned for the near future).</para>
  </listitem>
  <listitem>
    <para>portability: While the GiNaC library itself is designed
    to avoid any platform dependent features (it should compile
    on any ANSI compliant <literal>C++</literal> compiler), the
    currently used version of the CLN library (fast large integer and
    arbitrary precision arithmetics) can be compiled only on systems
    with a recently new <literal>C++</literal> compiler from the
    GNU Compiler Collection (<literal>GCC</literal>).  GiNaC uses
    recent language features like explicit constructors, mutable
    members, RTTI, dynamic_casts and STL, so ANSI compliance is meant
    literally.  Recent <literal>GCC</literal> versions starting at
    2.95, although itself not yet ANSI compliant, support all needed
    features.
    </para>
  </listitem>
</itemizedlist>
</para>

<sect1><title>Why <literal>C++</literal>?</title>

<para>Why did we choose to implement GiNaC in <literal>C++</literal>
instead of <literal>Java</literal> or any other language?
<literal>C++</literal> is not perfect: type checking is not strict
(casting is possible), separation between interface and implementation
is not complete, object oriented design is not enforced.  The main
reason is the often scolded feature of operator overloading in
<literal>C++</literal>. While it may be true that operating on classes
with a <literal>+</literal> operator is rarely meaningful, it is
perfectly suited for algebraic expressions. Writing 3x+5y as
<literal>3*x+5*y</literal> instead of
<literal>x.times(3).plus(y.times(5))</literal> looks much more
natural. Furthermore, the main developers are more familiar with
<literal>C++</literal> than with any other programming
language.</para>

</chapter>


<bibliography>
<bibliodiv>

<biblioentry>
  <bookbiblio>
    <title>ISO/IEC 14882:1998</title>
    <subtitle>Programming Languages: C++</subtitle>
  </bookbiblio>
</biblioentry>

<bibliomixed>
  <title>CLN: A Class Library for Numbers</title>
  <authorgroup>
    <author>
      <firstname>Bruno</firstname><surname>Haible</surname>
      <affiliation><address><email>haible@ilog.fr</email></address></affiliation>
    </author>
  </authorgroup>
</bibliomixed>

<biblioentry>
  <bookbiblio>
    <title>The C++ Programming Language</title>
    <authorgroup><author><firstname>Bjarne</firstname><surname>Stroustrup</surname></author></authorgroup>
    <edition>3</edition>
    <isbn>0-201-88954-4</isbn>
    <publisher><publishername>Addison Wesley</publishername></publisher>
  </bookbiblio>
</biblioentry>

<biblioentry>
  <bookbiblio>
    <title>C++ FAQs</title>
    <authorgroup><author><firstname>Marshall</firstname><surname>Cline</surname></author></authorgroup>
    <isbn>0-201-58958-3</isbn>
    <pubdate>1995</pubdate>
    <publisher><publishername>Addison Wesley</publishername></publisher>  
  </bookbiblio>
</biblioentry>

<biblioentry>
  <bookbiblio>
    <title>Algorithms for Computer Algebra</title>
    <authorgroup>
      <author><firstname>Keith</firstname><othername>O.</othername><surname>Geddes</surname></author>
      <author><firstname>Stephen</firstname><othername>R.</othername><surname>Czapor</surname></author>
      <author><firstname>George</firstname><surname>Labahn</surname></author>
    </authorgroup>
    <isbn>0-7923-9259-0</isbn>
    <pubdate>1992</pubdate>
    <publisher>
      <publishername>Kluwer Academic Publishers</publishername>
      <address><city>Norwell</city>, <state>Massachusetts</state></address>
    </publisher>
  </bookbiblio>
</biblioentry>

<biblioentry>
  <bookbiblio>
    <title>Computer Algebra</title>
    <subtitle>Systems and Algorithms for Algebraic Computation</subtitle>
    <authorgroup>
      <author><firstname>J.</firstname><othername>H.</othername><surname>Davenport</surname></author>
      <author><firstname>Y.</firstname><surname>Siret</surname></author>
      <author><firstname>E.</firstname><surname>Tournier</surname></author>
    </authorgroup>
    <isbn>0-12-204230-1</isbn>
    <pubdate>1988</pubdate>
    <publisher>
      <publishername>Academic Press</publishername>
      <address><city>London</city></address>
    </publisher>
  </bookbiblio>
</biblioentry>

</bibliodiv>
</bibliography>

</book>