Initial revision
[ginac.git] / doc / tutorial.sgml.in
1 <!DOCTYPE Book PUBLIC "-//Davenport//DTD DocBook V3.0//EN">
2
3 <book>
4 <title>GiNaC Tutorial</title>
5 <bookinfo>
6 <subtitle>An open framework for symbolic computation within the C++ programming language</subtitle>
7 <bookbiblio>
8 <authorgroup>
9   <collab>
10     <collabname>The GiNaC Group</collabname>
11   </collab>
12   <author>
13     <firstname>Christian</firstname><surname>Bauer</surname>
14     <affiliation>
15       <address><email>Christian.Bauer@Uni-Mainz.DE</email></address>
16     </affiliation>
17   </author>
18   <author>
19     <firstname>Alexander</firstname><surname>Frink</surname>
20     <affiliation>
21       <address><email>Alexander.Frink@Uni-Mainz.DE</email></address>
22     </affiliation>
23   </author>
24   <author>
25     <firstname>Richard</firstname><othername>B.</othername><surname>Kreckel</surname>
26     <affiliation>
27       <address><email>Richard.Kreckel@Uni-Mainz.DE</email></address>
28     </affiliation>
29   </author>
30   <author>
31     <surname>Others</surname>
32     <affiliation>
33       <address><email>whoever@ThEP.Physik.Uni-Mainz.DE</email></address>
34     </affiliation>
35   </author>
36 </authorgroup>
37 </bookbiblio>
38 </bookinfo>
39
40 <preface>
41 <title>Introduction</title>
42
43 <para>The motivation behind GiNaC derives from the observation that
44 most present day computer algebra systems (CAS) are linguistically and
45 semantically impoverished.  It is an attempt to overcome the current
46 situation by extending a well established and standardized computer
47 language (C++) by some fundamental symbolic capabilities, thus
48 allowing for integrated systems that embed symbolic manipulations
49 together with more established areas of computer science (like
50 computation-intense numeric applications, graphical interfaces, etc.)
51 under one roof.</para>
52
53 <para>This tutorial is intended for the novice user who is new to GiNaC
54 but already has some background in C++ programming.  However, since a
55 hand made documentation like this one is difficult to keep in sync
56 with the development the actual documentation is inside the sources in
57 the form of comments.  That documentation may be parsed by one of the
58 many Javadoc-like documentation systems.  The generated HTML
59 documenatation is included in the distributed sources (subdir
60 <literal>doc/reference/</literal>) or can be accessed directly at URL
61 <ulink
62 url="http://wwwthep.physik.uni-mainz.de/GiNaC/reference/"><literal>http://wwwthep.physik.uni-mainz.de/GiNaC/reference/</literal></ulink>.
63 It is an invaluable resource not only for the advanced user who wishes
64 to extend the system (or chase bugs) but for everybody who wants to
65 comprehend the inner workings of GiNaC.  This little tutorial on the
66 other hand only covers the basic things that are unlikely to change in
67 the near future.
68 </para>
69
70 <sect1><title>License</title>
71
72 <para>The GiNaC framework for symbolic computation within the C++
73 programming language is Copyright (C) 1999 Johannes Gutenberg
74 Universit&auml;t Mainz, Germany.</para>
75
76 <para>This program is free software; you can redistribute it and/or
77 modify it under the terms of the GNU General Public License as
78 published by the Free Software Foundation; either version 2 of the
79 License, or (at your option) any later version.</para>
80
81 <para>This program is distributed in the hope that it will be useful, but
82 WITHOUT ANY WARRANTY; without even the implied warranty of
83 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
84 General Public License for more details.</para>
85
86 <para>You should have received a copy of the GNU General Public License
87 along with this program; see the file COPYING.  If not, write to the
88 Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
89 MA 02111-1307, USA.</para>
90
91 </preface>
92
93 <chapter>
94 <title>A Tour of GiNaC</title>
95
96 <para>This quick tour of GiNaC wants to rise your interest in in the
97 subsequent chapters by showing off a bit.  Please excuse us if it
98 leaves many open questions.</para>
99
100 <sect1><title>How to use it from within C++</title> <para>The GiNaC
101 open framework for symbolic computation within the C++ programming
102 language does not try to define a language of it's own as conventional
103 CAS do.  Instead, it extends the capabilities of C++ by symbolic
104 manipulations.  Here is how to generate and print a simple (and
105 pointless) bivariate polynomial with some large coefficients:
106 <example>
107 <title>My first GiNaC program (a bivariate polynomial)</title>
108 <programlisting>
109 #include &lt;GiNaC/ginac.h&gt;
110
111 int main()
112 {
113     symbol x("x"), y("y");
114     ex poly;
115
116     for (int i=0; i<3; ++i)
117         poly += factorial(i+16)*pow(x,i)*pow(y,2-i);
118
119     cout &lt;&lt; poly &lt;&lt; endl;
120     return 0;
121 }
122 </programlisting>
123 <para>Assuming the file is called <literal>hello.cc</literal>, on 
124 our system we can compile and run it like this:</para>
125 <screen>
126 <prompt>sysprompt></prompt> c++ hello.cc -o hello -lcln -lginac
127 <prompt>sysprompt></prompt> ./hello
128 355687428096000*x*y+20922789888000*y^2+6402373705728000*x^2
129 </screen>
130 </example>
131 </para>
132
133 <para>Next, there is a more meaningful C++ program that calls a
134 function which generates Hermite polynomials in a specified free
135 variable.
136 <example>
137 <title>My second GiNaC program (Hermite polynomials)</title>
138 <programlisting>
139 #include &lt;GiNaC/ginac.h&gt;
140
141 ex HermitePoly(symbol x, int deg)
142 {
143     ex HKer=exp(-pow(x,2));
144     // uses the identity H_n(x) == (-1)^n exp(x^2) (d/dx)^n exp(-x^2) 
145     return normal(pow(-1,deg) * diff(HKer, x, deg) / HKer);
146 }
147
148 int main()
149 {
150     symbol z("z");
151
152     for (int i=0; i<6; ++i)
153         cout &lt;&lt; "H_" &lt;&lt; i &lt;&lt; "(z) == " &lt;&lt; HermitePoly(z,i) &lt;&lt; endl;
154
155     return 0;
156 }
157 </programlisting>
158 <para>When run, this will type out</para>
159 <screen>
160 H_0(z) == 1
161 H_1(z) == 2*z
162 H_2(z) == 4*z^2-2
163 H_3(z) == -12*z+8*z^3
164 H_4(z) == -48*z^2+16*z^4+12
165 H_5(z) == 120*z-160*z^3+32*z^5
166 </screen>
167 </example>
168 This method of generating the coefficients is of course far from
169 optimal for production purposes.</para>
170
171 <para>In order to show some more examples of what GiNaC can do we
172 will now use <literal>ginsh</literal>, a simple GiNaC interactive
173 shell that provides a convenient window into GiNaC's capabilities.
174 </para></sect1>
175
176 <sect1><title>What it can do for you</title>
177
178 <para>After invoking <literal>ginsh</literal> one can test and
179 experiment with GiNaC's features much like in other Computer Algebra
180 Systems except that it does not provide programming constructs like
181 loops or conditionals.  For a concise description of the
182 <literal>ginsh</literal> syntax we refer to its accompanied 
183 man-page.</para>
184
185 <para>It can manipulate arbitrary precision integers in a very fast
186 way.  Rational numbers are automatically converted to fractions of
187 coprime integers:
188 <screen>
189 > x=3^150;
190 369988485035126972924700782451696644186473100389722973815184405301748249
191 > y=3^149;
192 123329495011708990974900260817232214728824366796574324605061468433916083
193 > x/y;
194 3
195 > y/x;
196 1/3
197 </screen>
198 </para>
199
200 <para>All numbers occuring in GiNaC's expressions can be converted
201 into floating point numbers with the <literal>evalf</literal> method,
202 to arbitrary accuracy:
203 <screen>
204 > evalf(1/7);
205 0.14285714285714285714
206 > Digits=150;
207 150
208 > evalf(1/7);
209 0.1428571428571428571428571428571428571428571428571428571428571428571428
210 5714285714285714285714285714285714285
211 </screen>
212 </para>
213
214 <para>Exact numbers other than rationals that can be manipulated in
215 GiNaC include predefined constants like Archimedes' Pi.  They can both
216 be used in symbolic manipulations (as an exact number) as well as in
217 numeric expressions (as an inexact number):
218 <screen>
219 > a=Pi^2+x;
220 x+Pi^2
221 > evalf(a);
222 x+9.869604401089358619L0
223 > x=2;
224 2
225 > evalf(a);
226 11.869604401089358619L0
227 </screen>
228 </para>
229
230 <para>Built-in functions evaluate immediately to exact numbers if
231 this is possible.  Conversions that can be safely performed are done
232 immediately; conversions that are not generally valid are not done:
233 <screen>
234 > cos(42*Pi);
235 1
236 > cos(acos(x));
237 x
238 > acos(cos(x));
239 acos(cos(x))
240 </screen>
241 (Note that converting the last input to <literal>x</literal> would
242 allow one to conclude that <literal>42*Pi</literal> is equal to
243 <literal>0</literal>.)</para>
244
245 <para>Linear equation systems can be solved along with basic linear
246 algebra manipulations over symbolic expressions:
247 <screen>
248 > lsolve(a+x*y==z,x);
249 y^(-1)*(z-a);
250 lsolve([3*x+5*y == 7, -2*x+10*y == -5], [x, y]);
251 [x==19/8,y==-1/40]
252 > M = [[ [[1, 3]], [[-3, 2]] ]];
253 [[ [[1,3]], [[-3,2]] ]]
254 > determinant(M);
255 11
256 > charpoly(M,lambda);
257 lambda^2-3*lambda+11
258 </screen>
259 </para>
260
261 <para>Multivariate polynomials and rational functions may be expanded,
262 collected and normalized (i.e. converted to a ratio of two coprime 
263 polynomials):
264 <screen>
265 > a = x^4 + 2*x^2*y^2 + 4*x^3*y + 12*x*y^3 - 3*y^4;
266 -3*y^4+x^4+12*x*y^3+2*x^2*y^2+4*x^3*y
267 > b = x^2 + 4*x*y - y^2;
268 -y^2+x^2+4*x*y
269 > expand(a*b);
270 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
271 > collect(a*b,x);
272 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)
273 > normal(a/b);
274 3*y^2+x^2
275 </screen>
276 </para>
277
278 <para>
279 You can differentiate functions and expand them as Taylor or Laurent 
280 series (the third argument of series is the evaluation point, the 
281 fourth defines the order):
282 <screen>
283 > diff(tan(x),x);
284 tan(x)^2+1
285 > series(sin(x),x,0,4);
286 x-1/6*x^3+Order(x^4)
287 > series(1/tan(x),x,0,4);
288 x^(-1)-1/3*x+Order(x^2)
289 </screen>
290 </para>
291
292 </sect1>
293
294 </chapter>
295
296
297 <chapter>
298 <title>Installation</title>
299
300 <para>GiNaC's installation follows the spirit of most GNU software. It is
301 easily installed on your system by three steps: configuration, build,
302 installation.</para>
303
304 <sect1 id="ind123"><title id="CLN-main">Prerequistes</title>
305
306 <para>In order to install GiNaC on your system, some prerequistes need
307 to be met.  First of all, you need to have a C++-compiler adhering to
308 the ANSI-standard <citation>ISO/IEC 14882:1998(E)</citation>.  We used
309 <literal>GCC</literal> for development so if you have a different
310 compiler you are on your own.  For the configuration to succeed you
311 need a Posix compliant shell installed in <literal>/bin/sh</literal>,
312 GNU <literal>bash</literal> is fine.  Perl is needed by the built
313 process as well, since some of the source files are automatically
314 generated by Perl scripts.  Last but not least, Bruno Haible's library
315 <literal>CLN</literal> is extensively used and needs to be installed
316 on your system.  Please get it from <ulink
317 url="ftp://ftp.santafe.edu/pub/gnu/"><literal>ftp://ftp.santafe.edu/pub/gnu/</literal></ulink>
318 or from <ulink
319 url="ftp://ftp.ilog.fr/pub/Users/haible/gnu/"><literal>ftp://ftp.ilog.fr/pub/Users/haible/gnu/</literal></ulink>
320 (it is covered by GPL) and install it prior to trying to install
321 GiNaC.  The configure script checks if it can find it and if it cannot
322 it will refuse to continue.</para></sect1>
323
324 <sect1><title>Configuration</title>
325
326 <para>To configure GiNaC means to prepare the source distribution for
327 building.  It is done via a shell script called
328 <literal>configure</literal> that is shipped with the sources.
329 (Actually, this script is by itself created with GNU Autoconf from the
330 files <literal>configure.in</literal> and
331 <literal>aclocal.m4</literal>.)  Since a configure script generated by
332 GNU Autoconf never prompts, all customization must be done either via
333 command line parameters or environment variables.  It accepts a list
334 of parameters, the complete set of which can be listed by calling it
335 with the <literal>--help</literal> option.  The most important ones
336 will be shortly described in what follows:
337 <itemizedlist>
338   <listitem>
339     <para><literal>--enable-shared</literal>: When given, this option
340     switches on the build of a shared library, i.e. a
341     <literal>.so</literal>-file. A static libarary (i.e. a
342     <literal>.a</literal>-file) is still built. For this to succeed,
343     GNU libtool needs to be installed on your system. Hence,
344     <literal>configure</literal> checks if it can find an executable
345     <literal>libtool</literal> in the <literal>PATH</literal>. If it
346     doesn't this option is ignored and the default restored, which
347     means that only a static library will be build.</para>
348   </listitem>
349   <listitem>
350     <para><literal>--prefix=</literal><emphasis>PREFIX</emphasis>: The
351     directory where the compiled library and headers are installed. It
352     defaults to <literal>/usr/local</literal> which means that the
353     library is installed in the directory
354     <literal>/usr/local/lib</literal> and the header files in
355     <literal>/usr/local/include/GiNaC</literal> and the documentation
356     (like this one) into <literal>/usr/local/share/doc/GiNaC</literal>.</para>
357   </listitem>
358   <listitem>
359     <para><literal>--libdir=</literal><emphasis>LIBDIR</emphasis>: Use
360     this option in case you want to have the library installed in some
361     other directory than
362     <emphasis>PREFIX</emphasis><literal>/lib/</literal>.</para>
363   </listitem>
364   <listitem>
365     <para><literal>--includedir=</literal><emphasis>INCLUDEDIR</emphasis>:
366     Use this option in case you want to have the header files
367     installed in some other directory than
368     <emphasis>PREFIX</emphasis><literal>/include/GiNaC/</literal>. For
369     instance, if you specify
370     <literal>--includedir=/usr/include</literal> you will end up with
371     the header files sitting in the directory
372     <literal>/usr/include/GiNaC/</literal>. Note that the subdirectory
373     <literal>GiNaC</literal> is enforced by this process in order to
374     keep the header files separated from others.  This avoids some
375     clashes and allows for an easier deinstallation of GiNaC. This ought
376     to be considered A Good Thing (tm).</para>
377   </listitem>
378   <listitem>
379     <para><literal>--datadir=</literal><emphasis>DATADIR</emphasis>:
380     This option may be given in case you want to have the documentation 
381     installed in some other directory than
382     <emphasis>PREFIX</emphasis><literal>/share/doc/GiNaC/</literal>.
383   </listitem>
384 </itemizedlist>
385 </para>
386
387 <para>In addition, you may specify some environment variables.
388 <literal>CXX</literal> holds the path and the name of the C++ compiler
389 in case you want to override the default in your path.  (The
390 <literal>configure</literal> script searches your path for
391 <literal>c++</literal>, <literal>g++</literal>,
392 <literal>gcc</literal>, <literal>CC</literal>, <literal>cxx</literal>
393 and <literal>cc++</literal> in that order.)  It may be very useful to
394 define some compiler flags with the <literal>CXXFLAGS</literal>
395 environment variable, like optimization, debugging information and
396 warning levels.  If ommitted, it defaults to <literal>-g
397 -O2</literal>.</para>
398
399 <para>The whole process is illustrated in the following two
400 examples. (Substitute <literal>setenv VARIABLE value</literal> for
401 <literal>export VARIABLE=value</literal> if the Berkeley C shell is
402 your login shell.)
403
404 <example><title>Sample sessions of how to call the
405 configure-script</title> <para>Simple configuration for a site-wide
406 GiNaC library assuming everything is in default paths:</para>
407 <screen>
408 <prompt>sysprompt></prompt> export CXXFLAGS="-Wall -O2"
409 <prompt>sysprompt></prompt> ./configure --enable-shared
410 </screen>
411 <para>Configuration for a private GiNaC library with several
412 components sitting in custom places (site-wide <literal>GCC</literal>
413 and private <literal>CLN</literal>):</para>
414 <screen>
415 <prompt>sysprompt></prompt> export CXX=/usr/local/gnu/bin/c++
416 <prompt>sysprompt></prompt> export CPPFLAGS="${CPPFLAGS} -I${HOME}/include"
417 <prompt>sysprompt></prompt> export CXXFLAGS="${CXXFLAGS} -ggdb -Wall -ansi -pedantic -O2"
418 <prompt>sysprompt></prompt> export LDFLAGS="${LDFLAGS} -L${HOME}/lib"
419 <prompt>sysprompt></prompt> ./configure --enable-shared --prefix=${HOME}
420 </screen>
421 </example>
422 </para>
423
424 </sect1>
425
426 <sect1><title>Building GiNaC</title>
427
428 <para>After proper configuration you should just build the whole
429 library by typing <literal>make</literal> at the command
430 prompt and go for a cup of coffee.</para>
431
432 <para>Just to make sure GiNaC works properly you may run a simple test
433 suite by typing <literal>make check</literal>.  This will compile some
434 sample programs, run them and compare the output to reference output.
435 Each of the checks should return a message <literal>passed</literal>
436 together with the CPU time used for that particular test.  If it does
437 not, something went wrong.  This is mostly intended to be a check if
438 something was broken during the development, but not a sanity check of
439 your system.  Another intent is to allow people to fiddle around with
440 optimization.  If <literal>CLN</literal> was installed all right this
441 step is unlikely to return any errors.</para>
442
443 </sect1>
444
445 <sect1><title>Installation</title>
446
447 <para>To install GiNaC on your system, simply type <literal>make
448 install</literal>.  As described in the section about configuration
449 the files will be installed in the following directories (the
450 directories will be created if they don't already exist):
451 <itemizedlist>
452   <listitem>
453     <para><literal>libginac.a</literal> will go into
454     <emphasis>PREFIX</emphasis><literal>/lib/</literal> (or
455     <emphasis>LIBDIR</emphasis>) which defaults to
456     <literal>/usr/local/lib/</literal>.  So will
457     <literal>libginac.so</literal> if the the configure script was
458     given the option <literal>--enable-shared</literal>.  In that
459     case, the proper symlinks will be established as well (by running
460     <literal>ldconfig</literal>).</para>
461   </listitem>
462   <listitem>
463     <para>All the header files will be installed into
464     <emphasis>PREFIX</emphasis><literal>/include/GiNaC/</literal> (or
465     <emphasis>INCLUDEDIR</emphasis><literal>/GiNaC/</literal>, if
466     specified).</para>
467   </listitem>
468   <listitem>
469     <para>All documentation (HTML, Postscript and DVI) will be stuffed
470     into
471     <emphasis>PREFIX</emphasis><literal>/share/doc/GiNaC/</literal>
472     (or <emphasis>DATADIR</emphasis><literal>/doc/GiNaC/</literal>, if
473     specified).</para>
474   </listitem>
475 </itemizedlist>
476 </para>
477
478 <para>Just for the record we will list some other useful make targets:
479 <literal>make clean</literal> deletes all files generated by
480 <literal>make</literal>, i.e. all the object files.  In addition
481 <literal>make distclean</literal> removes all files generated by
482 configuration.  And finally <literal>make uninstall</literal> removes
483 the installed library and header files<footnoteref
484 linkend="warnuninstall-1">.  
485
486   <footnote id="warnuninstall-1"><para>Uninstallation does not work
487   after you have called <literal>make distclean</literal> since the
488   <literal>Makefile</literal> is itself generated by the configuration
489   from <literal>Makefile.in</literal> and hence deleted by
490   <literal>make distclean</literal>.  There are two obvious ways out
491   of this dilemma.  First, you can run the configuration again with
492   the same <emphasis>PREFIX</emphasis> thus creating a
493   <literal>Makefile</literal> with a working
494   <literal>uninstall</literal> target.  Second, you can do it by hand
495   since you now know where all the files went during
496   installation.</para></footnote>
497 </para>
498
499 </sect1>
500 </chapter>
501
502
503 <chapter>
504 <title>Basic Concepts</title>
505
506 <para>This chapter will describe the different fundamental objects
507 that can be handled with GiNaC.  But before doing so, it is worthwhile
508 introducing you to the more commonly used class of expressions,
509 representing a flexible meta-class for storing all mathematical
510 objects.</para>
511
512 <sect1><title>Expressions</title>
513
514 <para>The most common class of objects a user deals with is the
515 expression <literal>ex</literal>, representing a mathematical object
516 like a variable, number, function, sum, product, etc...  Expressions
517 may be put together to form new expressions, passed as arguments to
518 functions, and so on.  Here is a little collection of valid
519 expressions:
520 <example><title>Examples of expressions</title>
521 <programlisting>
522     ex MyEx1 = 5;                       // simple number
523     ex MyEx2 = x + 2*y;                 // polynomial in x and y
524     ex MyEx3 = (x + 1)/(x - 1);         // rational expression
525     ex MyEx4 = sin(x + 2*y) + 3*z + 41; // containing a function
526     ex MyEx5 = MyEx4 + 1;               // similar to above
527 </programlisting>
528 </example>
529 Before describing the more fundamental objects that form the building
530 blocks of expressions we'll have a quick look under the hood by
531 describing how expressions are internally managed.</para>
532
533 <sect2><title>Digression: Expressions are reference counted</title>
534
535 <para>An expression is extremely light-weight since internally it
536 works like a handle to the actual representation and really holds
537 nothing more than a pointer to some other object. What this means in
538 practice is that whenever you create two <literal>ex</literal> and set
539 the second equal to the first no copying process is involved. Instead,
540 the copying takes place as soon as you try to change the second.
541 Consider the simple sequence of code:
542 <example><title>Simple copy-on-write semantics</title>
543 <programlisting>
544 #include &lt;GiNaC/ginac.h&gt;
545
546 int main()
547 {
548     symbol x("x"), y("y"), z("z");
549     ex e1, e2;
550
551     e1 = sin(x + 2*y) + 3*z + 41;
552     e2 = e1;                // e2 points to same object as e1
553     cout &lt;&lt; e2 &lt;&lt; endl;     // prints sin(x+2*y)+3*z+41
554     e2 += 1;                // e2 is copied into a new object
555     cout &lt;&lt; e2 &lt;&lt; endl;     // prints sin(x+2*y)+3*z+42
556     // ...
557 }
558 </programlisting>
559 </example>
560 The line <literal>e2 = e1;</literal> creates a second expression
561 pointing to the object held already by <literal>e1</literal>.  The
562 time involved for this operation is therefore constant, no matter how
563 large <literal>e1</literal> was.  Actual copying, however, must take
564 place in the line <literal>e2 += 1</literal> because
565 <literal>e1</literal> and <literal>e2</literal> are not handles for
566 the same object any more.  This concept is called
567 <emphasis>copy-on-write semantics</emphasis>.  It increases
568 performance considerably whenever one object occurs multiple times and
569 represents a simple garbage collection scheme because when an
570 <literal>ex</literal> runs out of scope its destructor checks whether
571 other expressions handle the object it points to too and deletes the
572 object from memory if that turns out not to be the case.  A slightly
573 less trivial example of differentiation using the chain-rule should
574 make clear how powerful this can be.  <example><title>Advanced
575 copy-on-write semantics</title>
576 <programlisting>
577 #include &lt;GiNaC/ginac.h&gt;
578
579 int main()
580 {
581     symbol x("x"), y("y");
582
583     ex e1 = x + 3*y;
584     ex e2 = pow(e1, 3);
585     ex e3 = diff(sin(e2), x);   // first derivative of sin(e2) by x
586     cout &lt;&lt; e1 &lt;&lt; endl          // prints x+3*y
587          &lt;&lt; e2 &lt;&lt; endl          // prints (x+3*y)^3
588          &lt;&lt; e3 &lt;&lt; endl;         // prints 3*(x+3*y)^2*cos((x+3*y)^3)
589     // ...
590 }
591 </programlisting>
592 </example>
593 Here, <literal>e1</literal> will actually be referenced three times
594 while <literal>e2</literal> will be referenced two times.  When the
595 power of an expression is built, that expression needs not be
596 copied. Likewise, since the derivative of a power of an expression can
597 be easily expressed in terms of that expression, no copying of
598 <literal>e1</literal> is involved when <literal>e3</literal> is
599 constructed.  So, when <literal>e3</literal> is constructed it will
600 print as <literal>3*(x+3*y)^2*cos((x+3*y)^3)</literal> but the
601 argument of <literal>cos()</literal> only holds a reference to
602 <literal>e2</literal> and the factor in front is just
603 <literal>3*e1^2</literal>.
604 </para>
605
606 <para>As a user of GiNaC, you cannot see this mechanism of
607 copy-on-write semantics.  When you insert an expression into a
608 second expression, the result behaves exactly as if the contents of
609 the first expression were inserted.  But it may be useful to remember
610 that this is not what happens.  Knowing this will enable you to write
611 much more efficient code.</para>
612
613 <para>So much for expressions.  But what exactly are these expressions
614 handles of?  This will be answered in the following sections.</para>
615 </sect2>
616 </sect1>
617
618 <sect1><title>The Class Hierarchy</title>
619
620 <para>GiNaC's class hierarchy consists of several classes representing
621 mathematical objects, all of which (except for <literal>ex</literal>
622 and some helpers) are internally derived from one abstract base class
623 called <literal>basic</literal>.  You do not have to deal with objects
624 of class <literal>basic</literal>, instead you'll be dealing with
625 symbols and functions of symbols.  You'll soon learn in this chapter
626 how many of the functions on symbols are really classes.  This is
627 because simple symbolic arithmetic is not supported by languages like
628 C++ so in a certain way GiNaC has to implement its own arithmetic.</para>
629
630 <para>To give an idea about what kinds of symbolic composits may be
631 built we have a look at the most important classes in the class
632 hierarchy.  The dashed line symbolizes a "points to" or "handles"
633 relationship while the solid lines stand for "inherits from"
634 relationships.
635 <figure id="classhier-id" float="1">
636 <title>The GiNaC class hierarchy</title>
637   <graphic align="center" fileref="classhierarchy.graext" format="GRAEXT"></graphic>
638 </figure>
639 Some of the classes shown here (the ones sitting in white boxes) are
640 abstract base classes that are of no interest at all for the user.
641 They are used internally in order to avoid code duplication if
642 two or more classes derived from them share certain features.  An
643 example would be <literal>expairseq</literal>, which is a container
644 for a sequence of pairs each consisting of one expression and a number
645 (<literal>numeric</literal>).  What <emphasis>is</emphasis> visible to
646 the user are the derived classes <literal>add</literal> and
647 <literal>mul</literal>, representing sums of terms and products,
648 respectively.  We'll come back later to some more details about these
649 two classes and motivate the use of pairs in sums and products here.</para>
650
651 <sect2><title>Digression: Internal representation of products and sums</title>
652
653 <para>Although it should be completely transparent for the user of
654 GiNaC a short discussion of this topic helps understanding the sources
655 and also explains performance to a large degree.  Consider the
656 symbolic expression <literal>(a+2*b-c)*d</literal>, which could
657 naively be represented by a tree of linear containers for addition and
658 multiplication together with atomic leaves of symbols and integer
659 numbers in this fashion:
660 <figure id="repres-naive-id" float="1">
661 <title>Naive internal representation of <emphasis>d(a+2*b-c)</emphasis></title>
662   <graphic align="center" fileref="rep_naive.graext" format="GRAEXT"></graphic>
663 </figure>
664 However, doing so results in a rather deeply nested tree which will
665 quickly become rather slow to manipulate.  If we represent the sum
666 instead as a sequence of terms, each having a purely numeric
667 coefficient, the tree becomes much more flat.
668 <figure id="repres-pair-id" float="1">
669 <title>Better internal representation of <emphasis>d(a+2*b-c)</emphasis></title>
670   <graphic align="center" fileref="rep_pair.graext" format="GRAEXT"></graphic>
671 </figure>
672 The number <literal>1</literal> under the symbol <literal>d</literal>
673 is a hint that multiplication objects can be treated similarly where
674 the coeffiecients are interpreted as <emphasis>exponents</emphasis>
675 now.  Addition of sums of terms or multiplication of products with
676 numerical exponents can be made very efficient with a
677 pair-representation.  Internally, this handling is done by most CAS in
678 this way.  It typically speeds up manipulations by an order of
679 magnitude.  Now it should be clear, why both classes
680 <literal>add</literal> and <literal>mul</literal> are derived from the
681 same abstract class: the representation is the same, only the
682 interpretation differs.  </para>
683
684 </sect1>
685
686 <sect1><title>Symbols</title>
687
688 <para>Symbols are for symbolic manipulation what atoms are for
689 chemistry.  You can declare objects of type symbol as any other object
690 simply by saying <literal>symbol x,y;</literal>.  There is, however, a
691 catch in here having to do with the fact that C++ is a compiled
692 language.  The information about the symbol's name is thrown away by
693 the compiler but at a later stage you may want to print expressions
694 holding your symbols.  In order to avoid confusion GiNaC's symbols are
695 able to know their own name.  This is accompilshed by declaring its
696 name for output at construction time in the fashion <literal>symbol
697 x("x");</literal>.</para>
698
699 <para>Although symbols can be assigned expressions for internal
700 reasons, you should not do it (and we are not going to tell you how it
701 is done).  If you want to replace a symbol with something else in an
702 expression, you can use the expression's <literal>.subs()</literal>
703 method.</para>
704
705 </sect1>
706
707 <sect1><title>Numbers</title>
708
709 <para>For storing numerical things, GiNaC uses Bruno Haible's library
710 <literal>CLN</literal>.  The classes therein serve as foundation
711 classes for GiNaC.  <literal>CLN</literal> stands for Class Library
712 for Numbers or alternatively for Common Lisp Numbers.  In order to
713 find out more about <literal>CLN</literal>'s internals the reader is
714 refered to the documentation of that library.  Suffice to say that it
715 is by itself build on top of another library, the GNU Multiple
716 Precision library <literal>GMP</literal>, which is a extremely fast
717 library for arbitrary long integers and rationals as well as arbitrary
718 precision floating point numbers.  It is very commonly used by several
719 popular cryptographic applications.  <literal>CLN</literal> extends
720 <literal>GMP</literal> by several useful things: First, it introduces
721 the complex number field over either reals (i.e. floating point
722 numbers with arbitrary precision) or rationals.  Second, it
723 automatically converts rationals to integers if the denominator is
724 unity and complex numbers to real numbers if the imaginary part
725 vanishes and also correctly treats algebraic functions.  Third it
726 provides good implementations of state-of-the-art algorithms for all
727 trigonometric and hyperbolic functions as well as for calculation of
728 some useful constants.</para>
729
730 <para>The user can construct an object of class
731 <literal>numeric</literal> in several ways.  The following example
732 shows the four most important constructors: construction from
733 C-integer, construction of fractions from two integers, construction
734 from C-float and construction from a string.
735 <example><title>Sample C++ program</title>
736 <programlisting>
737 #include &lt;GiNaC/ginac.h&gt;
738
739 int main()
740 {
741     numeric two(2);                     // exact integer 2
742     numeric r(2,3);                     // exact fraction 2/3
743     numeric e(2.71828);                 // floating point number
744     numeric p("3.1415926535897932385"); // floating point number
745
746     cout &lt;&lt; two*p &lt;&lt; endl;  // floating point 6.283...
747     // ...
748 }
749 </programlisting>
750 </example>
751 Note that all those constructors are <emphasis>explicit</emphasis>
752 which means you are not allowed to write <literal>numeric
753 two=2;</literal>.  This is because the basic objects to be handled by
754 GiNaC are the expressions and we want to keep things simple and wish
755 objects like <literal>pow(x,2)</literal> to be handled the same way
756 as <literal>pow(x,a)</literal>, which means that we need to allow a
757 general expression as base and exponent.  Therefore there is an
758 implicit construction from a C-integer directly to an expression
759 handling a numeric in the first example.  This design really becomes
760 convenient when one declares own functions having more than one
761 parameter but it forbids using implicit constructors because that
762 would lead to ambiguities.
763 </para>
764
765 <para>We have seen now the distinction between exact numbers and
766 floating point numbers.  Clearly, the user should never have to worry
767 about dynamically created exact numbers, since their "exactness"
768 always determines how they ought to be handled.  The situation is
769 different for floating point numbers.  Their accuracy is handled by
770 one <emphasis>global</emphasis> variable, called
771 <literal>Digits</literal>.  (For those readers who know about Maple:
772 it behaves very much like Maple's <literal>Digits</literal>).  All
773 objects of class numeric that are constructed from then on will be
774 stored with a precision matching that number of decimal digits:
775 <example><title>Controlling the precision of floating point numbers</title>
776 <programlisting> 
777 #include
778 &lt;GiNaC/ginac.h&gt;
779
780 void foo()
781 {
782     numeric three(3.0), one(1.0);
783     numeric x = one/three;
784
785     cout &lt;&lt; "in " &lt;&lt; Digits &lt;&lt; " digits:" &lt;&lt; endl;
786     cout &lt;&lt; x &lt;&lt; endl;
787     cout &lt;&lt; Pi.evalf() &lt;&lt; endl;
788 }
789
790 int main()
791 {
792     foo();
793     Digits = 60;
794     foo();
795     return 0;
796 }
797 </programlisting>
798 </example>
799 The above example prints the following output to screen:
800 <screen>
801 in 17 digits:
802 0.333333333333333333
803 3.14159265358979324
804 in 60 digits:
805 0.333333333333333333333333333333333333333333333333333333333333333333
806 3.14159265358979323846264338327950288419716939937510582097494459231
807 </screen>
808 </para>
809
810 <sect2><title>Tests on numbers</title>
811
812 <para>Once you have declared some numbers, assigned them to
813 expressions and done some arithmetic with them it is frequently
814 desired to retrieve some kind of information from them like asking
815 whether that number is integer, rational, real or complex.  For those
816 cases GiNaC provides several useful methods.  (Internally, they fall
817 back to invocations of certain CLN functions.)</para>
818
819 <para>As an example, let's construct some rational number, multiply it
820 with some multiple of its denominator and check what comes out:
821 <example><title>Sample test on objects of type numeric</title>
822 <programlisting>
823 #include &lt;GiNaC/ginac.h&gt;
824
825 int main()
826 {
827     numeric twentyone(21);
828     numeric ten(10);
829     numeric answer(21,5);
830
831     cout &lt;&lt; answer.is_integer() &lt;&lt; endl;  // false, it's 21/5
832     answer *= ten;
833     cout &lt;&lt; answer.is_integer() &lt;&lt; endl;  // true, it's 42 now!
834     // ...
835 }
836 </programlisting>
837 </example>
838 Note that the variable <literal>answer</literal> is constructed here
839 as an integer but in an intermediate step it holds a rational number
840 represented as integer numerator and denominator.  When multiplied by
841 10, the denominator becomes unity and the result is automatically
842 converted to a pure integer again.  Internally, the underlying
843 <literal>CLN</literal> is responsible for this behaviour and we refer
844 the reader to <literal>CLN</literal>'s documentation.  Suffice to say
845 that the same behaviour applies to complex numbers as well as return
846 values of certain functions.  Complex numbers are automatically
847 converted to real numbers if the imaginary part becomes zero.  The
848 full set of tests that can be applied is listed in the following
849 table.
850 <informaltable colsep="0" frame="topbot" pgwide="1">
851 <tgroup cols="2">
852 <colspec colnum="1" colwidth="1*">
853 <colspec colnum="2" colwidth="2*">
854 <thead>
855   <row>
856     <entry>Method</entry>
857     <entry>Returns true if...</entry>
858   </row>
859 </thead>
860 <tbody>
861   <row>
862     <entry><literal>.is_zero()</literal></entry>
863     <entry>object is equal to zero</entry>
864   </row>
865   <row>
866     <entry><literal>.is_positive()</literal></entry>
867     <entry>object is not complex and greater than 0</entry>
868   </row>
869   <row>
870     <entry><literal>.is_integer()</literal></entry>
871     <entry>object is a (non-complex) integer</entry>
872   </row>
873   <row>
874     <entry><literal>.is_pos_integer()</literal></entry>
875     <entry>object is an integer and greater than 0</entry>
876   </row>
877   <row>
878     <entry><literal>.is_nonneg_integer()</literal></entry>
879     <entry>object is an integer and greater equal 0</entry>
880   </row>
881   <row>
882     <entry><literal>.is_even()</literal></entry>
883     <entry>object is an even integer</entry>
884   </row>
885   <row>
886     <entry><literal>.is_odd()</literal></entry>
887     <entry>object is an odd integer</entry>
888   </row>
889   <row>
890     <entry><literal>.is_prime()</literal></entry>
891     <entry>object is a prime integer (probabilistic primality test)</entry>
892   </row>
893   <row>
894     <entry><literal>.is_rational()</literal></entry>
895     <entry>object is an exact rational number (integers are rational, too, as are complex extensions like <literal>2/3+7/2*I</literal>)</entry>
896   </row>
897   <row>
898     <entry><literal>.is_real()</literal></entry>
899     <entry>object is a real integer, rational or float (i.e. is not complex)</entry>
900   </row>
901 </tbody>
902 </tgroup>
903 </informaltable>
904 </para>
905
906 </sect2>
907
908 </sect1>
909
910
911 <sect1><title>Constants</title>
912
913 <para>Constants behave pretty much like symbols except that that they return
914 some specific number when the method <literal>.evalf()</literal> is called.
915 </para>
916
917 <para>The predefined known constants are:
918 <informaltable colsep="0" frame="topbot" pgwide="1">
919 <tgroup cols="3">
920 <colspec colnum="1" colwidth="1*">
921 <colspec colnum="2" colwidth="2*">
922 <colspec colnum="3" colwidth="4*">
923 <thead>
924   <row>
925     <entry>Name</entry>
926     <entry>Common Name</entry>
927     <entry>Numerical Value (35 digits)</entry>
928   </row>
929 </thead>
930 <tbody>
931   <row>
932     <entry><literal>Pi</literal></entry>
933     <entry>Archimedes' constant</entry>
934     <entry>3.14159265358979323846264338327950288</entry>
935   </row><row>
936     <entry><literal>Catalan</literal></entry>
937     <entry>Catalan's constant</entry>
938     <entry>0.91596559417721901505460351493238411</entry>
939   </row><row>
940     <entry><literal>EulerGamma</literal></entry>
941     <entry>Euler's (or Euler-Mascheroni) constant</entry>
942     <entry>0.57721566490153286060651209008240243</entry>
943   </row>
944 </tbody>
945 </tgroup>
946 </informaltable>
947 </para>
948
949 </sect1>
950
951 <sect1><title>Fundamental operations: The <literal>power</literal>, <literal>add</literal> and <literal>mul</literal> classes</title>
952
953 <para>Simple polynomial expressions are written down in GiNaC pretty
954 much like in other CAS.  The necessary operators <literal>+</literal>,
955 <literal>-</literal>, <literal>*</literal> and <literal>/</literal>
956 have been overloaded to achieve this goal.  When you run the following
957 program, the constructor for an object of type <literal>mul</literal>
958 is automatically called to hold the product of <literal>a</literal>
959 and <literal>b</literal> and then the constructor for an object of
960 type <literal>add</literal> is called to hold the sum of that
961 <literal>mul</literal> object and the number one:
962 <example><title>Construction of <literal>add</literal> and <literal>mul</literal> objects</title>
963 <programlisting>
964 #include &lt;GiNaC/ginac.h&gt;
965
966 int main()
967 {
968     symbol a("a"), b("b");
969     ex MyTerm = 1+a*b;
970     // ...
971 }
972 </programlisting>
973 </example></para>
974
975 <para>For exponentiation, you have already seen the somewhat clumsy
976 (though C-ish) statement <literal>pow(x,2);</literal> to represent
977 <literal>x</literal> squared.  This direct construction is necessary
978 since we cannot safely overload the constructor <literal>^</literal>
979 in <literal>C++</literal> to construct a <literal>power</literal>
980 object.  If we did, it would have two counterintuitive effects:
981 <itemizedlist>
982   <listitem>
983     <para>Due to <literal>C</literal>'s operator precedence,
984     <literal>2*x^2</literal> would be parsed as <literal>(2*x)^2</literal>.
985   </listitem>
986   <listitem>
987     <para>Due to the binding of the operator <literal>^</literal>, 
988     <literal>x^2^3</literal> would result in <literal>x^8</literal>. 
989     This would be confusing since most (though not all) other CAS 
990     interpret this as <literal>x^6</literal>.</para>
991   </listitem>
992 </itemizedlist>
993 Both effects are contrary to mathematical notation and differ from the
994 way most other CAS handle exponentiation, therefore overloading
995 <literal>^</literal> is ruled out.  (Also note, that the other
996 frequently used exponentiation operator <literal>**</literal> does not
997 exist at all in <literal>C++</literal>).</para>
998
999 <para>To be somewhat more precise, objects of the three classes
1000 described here, are all containers for other expressions.  An object
1001 of class <literal>power</literal> is best viewed as a container with
1002 two slots, one for the basis, one for the exponent.  All valid GiNaC
1003 expressions can be inserted.  However, basic transformations like
1004 simplifying <literal>pow(pow(x,2),3)</literal> to
1005 <literal>x^6</literal> automatically are only performed when
1006 this is mathematically possible.  If we replace the outer exponent
1007 three in the example by some symbols <literal>a</literal>, the
1008 simplification is not safe and will not be performed, since
1009 <literal>a</literal> might be <literal>1/2</literal> and
1010 <literal>x</literal> negative.</para>
1011
1012 <para>Objects of type <literal>add</literal> and
1013 <literal>mul</literal> are containers with an arbitrary number of
1014 slots for expressions to be inserted.  Again, simple and safe
1015 simplifications are carried out like transforming
1016 <literal>3*x+4-x</literal> to <literal>2*x+4</literal>.</para>
1017
1018 <para>The general rule is that when you construct such objects, GiNaC
1019 automatically creates them in canonical form, which might differ from
1020 the form you typed in your program.  This allows for rapid comparison
1021 of expressions, since after all <literal>a-a</literal> is simply zero.
1022 Note, that the canonical form is not necessarily lexicographical
1023 ordering or in any way easily guessable.  It is only guaranteed that
1024 constructing the same expression twice, either implicitly or
1025 explicitly, results in the same canonical form.</para>
1026
1027 </sect1>
1028
1029 <sect1><title>Built-in Functions</title>
1030
1031 <para>This chapter is not here yet</para>
1032
1033
1034
1035 </sect1>
1036
1037 </chapter>
1038
1039
1040 <chapter>
1041 <title>Important Algorithms</title>
1042
1043 <para>In this chapter the most important algorithms provided by GiNaC
1044 will be described.  Some of them are implemented as functions on
1045 expressions, others are implemented as methods provided by expression
1046 objects.  If they are methods, there exists a wrapper function around
1047 it, so you can alternatively call it in a functional way as shown in
1048 the simple example:
1049 <example><title>Methods vs. wrapper functions</title>
1050 <programlisting>
1051 #include &lt;GiNaC/ginac.h&gt;
1052
1053 int main()
1054 {
1055     ex x = numeric(1.0);
1056     
1057     cout &lt;&lt; "As method:   " &lt;&lt; sin(x).evalf() &lt;&lt; endl;
1058     cout &lt;&lt; "As function: " &lt;&lt; evalf(sin(x)) &lt;&lt; endl;
1059     // ...
1060 }
1061 </programlisting>
1062 </example>
1063 The general rule is that wherever methods accept one or more
1064 parameters (<emphasis>arg1</emphasis>, <emphasis>arg2</emphasis>, ...)
1065 the order of arguments the function wrapper accepts is the same but
1066 preceded by the object to act on (<emphasis>object</emphasis>,
1067 <emphasis>arg1</emphasis>, <emphasis>arg2</emphasis>, ...).  This
1068 approach is the most natural one in an OO model but it may lead to
1069 confusion for MapleV users because where they would type
1070 <literal>A:=x+1; subs(x=2,A);</literal> GiNaC would require
1071 <literal>A=x+1; subs(A,x==2);</literal> (after proper declaration of A
1072 and x).  On the other hand, since MapleV returns 3 on
1073 <literal>A:=x^2+3; coeff(A,x,0);</literal> (GiNaC:
1074 <literal>A=pow(x,2)+3; coeff(A,x,0);</literal>) it is clear that
1075 MapleV is not trying to be consistent here.  Also, users of MuPAD will
1076 in most cases feel more comfortable with GiNaC's convention.  All
1077 function wrappers are always implemented as simple inline functions
1078 which just call the corresponding method and are only provided for
1079 users uncomfortable with OO who are dead set to avoid method
1080 invocations.  Generally, a chain of function wrappers is much harder
1081 to read than a chain of methods and should therefore be avoided if
1082 possible.  On the other hand, not everything in GiNaC is a method on
1083 class <literal>ex</literal> and sometimes calling a function cannot be
1084 avoided.
1085 </para>
1086
1087 <sect1><title>Polynomial Expansion</title>
1088
1089 <para>A polynomial in one or more variables has many equivalent
1090 representations.  Some useful ones serve a specific purpose.  Consider
1091 for example the trivariate polynomial <literal>4*x*y + x*z + 20*y^2 +
1092 21*y*z + 4*z^2</literal>.  It is equivalent to the factorized
1093 polynomial <literal>(x + 5*y + 4*z)*(4*y + z)</literal>.  Other
1094 representations are the recursive ones where one collects for
1095 exponents in one of the three variable.  Since the factors are
1096 themselves polynomials in the remaining two variables the procedure
1097 can be repeated.  In our expample, two possibilies would be
1098 <literal>(4*y + z)*x + 20*y^2 + 21*y*z + 4*z^2</literal> and
1099 <literal>20*y^2 + (21*z + 4*x)*y + 4*z^2 + x*z</literal>.
1100 </para>
1101
1102 <para>To bring an expression into expanded form, its method
1103 <function>.expand()</function> may be called.  In our example above,
1104 this corresponds to <literal>4*x*y + x*z + 20*y^2 + 21*y*z +
1105 4*z^2</literal>.  There is no canonical form in GiNaC.  Be prepared to
1106 see different orderings of terms in such sums!  </para>
1107
1108 </sect1>
1109
1110 <sect1><title>Collecting expressions</title>
1111
1112 <para>Another useful representation of multivariate polynomials is as
1113 a univariate polynomial in one of the variables with the coefficients
1114 being polynomials in the remaining variables.  The method
1115 <literal>collect()</literal> accomplishes this task:
1116 <funcsynopsis>
1117   <funcsynopsisinfo>#include &lt;GiNaC/ginac.h></funcsynopsisinfo>
1118   <funcdef>ex <function>ex::collect</function></funcdef>
1119   <paramdef>symbol const & <parameter>s</parameter></paramdef>
1120 </funcsynopsis>
1121 Note that the original polynomial needs to be in expanded form in
1122 order to be able to find the coefficients properly.  The range of
1123 occuring coefficients can be checked using the two methods
1124 <funcsynopsis>
1125   <funcsynopsisinfo>#include &lt;GiNaC/ginac.h></funcsynopsisinfo>
1126   <funcdef>int <function>ex::degree</function></funcdef>
1127   <paramdef>symbol const & <parameter>s</parameter></paramdef>
1128 </funcsynopsis>
1129 <funcsynopsis>
1130   <funcdef>int <function>ex::ldegree</function></funcdef>
1131   <paramdef>symbol const & <parameter>s</parameter></paramdef>
1132 </funcsynopsis>
1133 where <literal>degree()</literal> returns the highest coefficient and
1134 <literal>ldegree()</literal> the lowest one.  These two methods work
1135 also reliably on non-expanded input polynomials.  This is illustrated
1136 in the following example: 
1137
1138 <example><title>Collecting expressions in multivariate polynomials</title>
1139 <programlisting>
1140 #include &lt;GiNaC/ginac.h&gt;
1141
1142 int main()
1143 {
1144     symbol x("x"), y("y");
1145     ex PolyInp = 4*pow(x,3)*y + 5*x*pow(y,2) + 3*y
1146                  - pow(x+y,2) + 2*pow(y+2,2) - 8;
1147     ex Poly = PolyInp.expand();
1148     
1149     for (int i=Poly.ldegree(x); i<=Poly.degree(x); ++i) {
1150         cout &lt;&lt; "The x^" &lt;&lt; i &lt;&lt; "-coefficient is "
1151              &lt;&lt; Poly.coeff(x,i) &lt;&lt; endl;
1152     }
1153     cout &lt;&lt; "As polynomial in y: " 
1154          &lt;&lt; Poly.collect(y) &lt;&lt; endl;
1155     // ...
1156 }
1157 </programlisting>
1158 </example>
1159 When run, it returns an output in the following fashion:
1160 <screen>
1161 The x^0-coefficient is y^2+11*y
1162 The x^1-coefficient is 5*y^2-2*y
1163 The x^2-coefficient is -1
1164 The x^3-coefficient is 4*y
1165 As polynomial in y: -x^2+(5*x+1)*y^2+(-2*x+4*x^3+11)*y
1166 </screen>
1167 As always, the exact output may vary between different versions of
1168 GiNaC or even from run to run since the internal canonical ordering is
1169 not within the user's sphere of influence.</para>
1170
1171 </sect1>
1172
1173 <sect1 id="gcd-main"><title>Polynomial Arithmetic</title>
1174
1175 <sect2><title>GCD and LCM</title>
1176
1177 <para>The functions for polynomial greatest common divisor and least common
1178 multiple have the synopsis:
1179 <funcsynopsis>
1180   <funcsynopsisinfo>#include &lt;GiNaC/normal.h></funcsynopsisinfo>
1181   <funcdef>ex <function>gcd</function></funcdef>
1182   <paramdef>const ex *<parameter>a</parameter>, const ex *<parameter>b</parameter></paramdef>
1183 </funcsynopsis>
1184 <funcsynopsis>
1185   <funcdef>ex <function>lcm</function></funcdef>
1186   <paramdef>const ex *<parameter>a</parameter>, const ex *<parameter>b</parameter></paramdef>
1187 </funcsynopsis></para>
1188
1189 <para>The functions <function>gcd()</function> and <function
1190 id="lcm-main">lcm()</function> accepts two expressions
1191 <literal>a</literal> and <literal>b</literal> as arguments and return
1192 a new expression, their greatest common divisor or least common
1193 multiple, respectively.  If the polynomials <literal>a</literal> and
1194 <literal>b</literal> are coprime <function>gcd(a,b)</function> returns 1
1195 and <function>lcm(a,b)</function> returns the product of
1196 <literal>a</literal> and <literal>b</literal>.
1197 <example><title>Polynomal GCD/LCM</title>
1198 <programlisting>
1199 #include &lt;GiNaC/ginac.h&gt;
1200
1201 int main()
1202 {
1203     symbol x("x"), y("y"), z("z");
1204     ex P_a = 4*x*y + x*z + 20*pow(y, 2) + 21*y*z + 4*pow(z, 2);
1205     ex P_b = x*y + 3*x*z + 5*pow(y, 2) + 19*y*z + 12*pow(z, 2);
1206
1207     ex P_gcd = gcd(P_a, P_b);
1208     // x + 5*y + 4*z
1209     ex P_lcm = lcm(P_a, P_b);
1210     // 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
1211     // ...
1212 }
1213 </programlisting>
1214 </example>
1215 </para>
1216
1217 </sect2>
1218
1219 <sect2><title>The <function>normal</function> method</title>
1220
1221 <para>While in common symbolic code <function>gcd()</function> and
1222 <function>lcm()</function> are not too heavily used, some basic
1223 simplification occurs frequently.  Therefore
1224 <function>.normal()</function>, which provides some basic form of
1225 simplification, has become a method of class <literal>ex</literal>,
1226 just like <literal>.expand()</literal>.</para>
1227
1228 </sect2>
1229
1230 </sect1>
1231
1232 <sect1><title>Symbolic Differentiation</title>
1233
1234 <para>
1235 <example><title>Simple polynomial differentiation</title>
1236 <programlisting>
1237 #include &lt;GiNaC/ginac.h&gt;
1238
1239 int main()
1240 {
1241     symbol x("x"), y("y"), z("z");
1242     ex P = pow(x, 5) + pow(x, 2) + y;
1243
1244     cout &lt;&lt; P.diff(x,2) &lt;&lt; endl;  // 20*x^3 + 2
1245     cout &lt;&lt; P.diff(y) &lt;&lt; endl;    // 1
1246     cout &lt;&lt; P.diff(z) &lt;&lt; endl;    // 0
1247     // ...
1248 }
1249 </programlisting>
1250 </example>
1251 </para>
1252
1253 <para>
1254 <example><title>Differentiation with nontrivial functions</title>
1255 <programlisting>
1256 #include &lt;GiNaC/ginac.h&gt;
1257
1258 int main()
1259 {
1260     // To Be Done...
1261 }
1262 </programlisting>
1263 </example>
1264 </para>
1265
1266 </sect1>
1267
1268 <sect1><title>Series Expansion</title>
1269
1270 <para>Expressions know how to expand themselfes as a Taylor series or
1271 (more generally) a Laurent series.  As in most conventional Computer
1272 Algebra Systems no distinction is made between those two.  There is a
1273 class of its own for storing such series as well as a class for
1274 storing the order of the series.  A sample program could read:
1275 <example><title>Series expansion</title>
1276 <programlisting>
1277 #include &lt;GiNaC/ginac.h&gt;
1278
1279 int main()
1280 {
1281     symbol x("x");
1282     numeric point(0);
1283     ex MyExpr1 = sin(x);
1284     ex MyExpr2 = 1/(x - pow(x, 2) - pow(x, 3));
1285     ex MyTailor, MySeries;
1286     
1287     MyTailor = MyExpr1.series(x, numZERO(), 5);
1288     cout &lt;&lt; MyExpr1 &lt;&lt; " == " &lt;&lt; MyTailor
1289          &lt;&lt; " for small " &lt;&lt; x &lt;&lt; endl;
1290     MySeries = MyExpr2.series(x, numZERO(), 7);
1291     cout &lt;&lt; MyExpr2 &lt;&lt; " == " &lt;&lt; MySeries
1292          &lt;&lt; " for small " &lt;&lt; x &lt;&lt; endl;
1293     \\ ...
1294 }
1295 </programlisting>
1296 </example>
1297 </para>
1298
1299 </sect1>
1300
1301 </chapter>
1302
1303
1304 <chapter>
1305 <title>Extending GiNaC</title>
1306
1307 <para>Longish chapter follows here.</para>
1308
1309 </chapter>
1310
1311
1312 <chapter>
1313 <title>A Comparison with other CAS</title>
1314
1315 <para>This chapter will give you some information on how GiNaC
1316 compares to other, traditional Computer Algebra Systems, like
1317 <literal>Maple</literal>, <literal>Mathematica</literal> or
1318 <literal>Reduce</literal>, where it has advantages and disadvantages
1319 over these systems.</para>
1320
1321 <sect1><title>Advantages</title>
1322
1323 <para>GiNaC has several advantages over traditional Computer
1324 Algebra Systems, like 
1325
1326 <itemizedlist>
1327   <listitem>
1328     <para>familiar language: all common CAS implement their own
1329     proprietary grammar which you have to learn first (and maybe learn
1330     again when your vendor chooses to "enhance" it).  With GiNaC you
1331     can write your program in common <literal>C++</literal>, which is
1332     standardized.</para>
1333   </listitem>
1334   <listitem>
1335     <para>structured data types: you can build up structured data
1336     types using <literal>struct</literal>s or <literal>class</literal>es
1337     together with STL features instead of using unnamed lists of lists
1338     of lists.</para>
1339   </listitem>
1340   <listitem>
1341     <para>strongly typed: in CAS, you usually have only one kind of
1342     variables which can hold contents of an arbitrary type.  This
1343     4GL like feature is nice for novice programmers, but dangerous.
1344     </para>
1345   </listitem>
1346   <listitem>
1347     <para>development tools: powerful development tools exist for
1348     <literal>C++</literal>, like fancy editors (e.g. with automatic
1349     indentation and syntax highlighting), debuggers, visualization
1350     tools, documentation tools...</para>
1351   </listitem>
1352   <listitem>
1353     <para>modularization: <literal>C++</literal> programs can 
1354     easily be split into modules by separating interface and
1355     implementation.</para>
1356   </listitem>
1357   <listitem>
1358     <para>price: GiNaC is distributed under the GNU Public License
1359     which means that it is free and available with source code.  And
1360     there are excellent <literal>C++</literal>-compilers for free, too.
1361     </para>
1362   </listitem>
1363   <listitem>
1364     <para>extendable: you can add your own classes to GiNaC, thus
1365     extending it on a very low level.  Compare this to a traditional
1366     CAS that you can usually only extend on a high level by writing in
1367     the language defined by the parser.  In particular, it turns out
1368     to be almost impossible to fix bugs in a traditional system.
1369   </listitem>
1370   <listitem>
1371     <para>seemless integration: it is somewhere between difficult
1372     and impossible to call CAS functions from within a program 
1373     written in <literal>C++</literal> or any other programming 
1374     language and vice versa.  With GiNaC, your symbolic routines
1375     are part of your program.  You can easily call third party
1376     libraries, e.g. for numerical evaluation or graphical 
1377     interaction.  All other approaches are much more cumbersome: they
1378     range from simply ignoring the problem
1379     (i.e. <literal>Maple</literal>) to providing a
1380     method for "embedding" the system
1381     (i.e. <literal>Yacas</literal>).</para>
1382   </listitem>
1383   <listitem>
1384     <para>efficiency: often large parts of a program do not need
1385     symbolic calculations at all.  Why use large integers for loop
1386     variables or arbitrary precision arithmetics where double
1387     accuracy is sufficient?  For pure symbolic applications,
1388     GiNaC is comparable in speed with other CAS.
1389   </listitem>
1390 </itemizedlist>
1391 </para>
1392
1393 <sect1><title>Disadvantages</title>
1394
1395 <para>Of course it also has some disadvantages
1396
1397 <itemizedlist>
1398   <listitem>
1399     <para>not interactive: GiNaC programs have to be written in 
1400     an editor, compiled and executed. You cannot play with 
1401     expressions interactively.  However, such an extension is not
1402     inherently forbidden by design.  In fact, two interactive
1403     interfaces are possible: First, a simple shell that exposes GiNaC's
1404     types to a command line can readily be written (and has been
1405     written) and second, as a more consistent approach we plan
1406     an integration with the <literal>CINT</literal>
1407     <literal>C++</literal> interpreter.</para>
1408   </listitem>
1409   <listitem>
1410     <para>advanced features: GiNaC cannot compete with a program
1411     like <literal>Reduce</literal> which exists for more than
1412     30 years now or <literal>Maple</literal> which grows since 
1413     1981 by the work of dozens of programmers, with respect to
1414     mathematical features. Integration, factorization, non-trivial
1415     simplifications, limits etc. are missing in GiNaC (and are not
1416     planned for the near future).</para>
1417   </listitem>
1418   <listitem>
1419     <para>portability: While the GiNaC library itself is designed
1420     to avoid any platform dependent features (it should compile
1421     on any ANSI compliant <literal>C++</literal> compiler), the
1422     currently used version of the CLN library (fast large integer and
1423     arbitrary precision arithmetics) can be compiled only on systems
1424     with a recently new <literal>C++</literal> compiler from the
1425     GNU Compiler Collection (<literal>GCC</literal>).  GiNaC uses
1426     recent language features like explicit constructors, mutable
1427     members, RTTI, dynamic_casts and STL, so ANSI compliance is meant
1428     literally.  Recent <literal>GCC</literal> versions starting at
1429     2.95, although itself not yet ANSI compliant, support all needed
1430     features.
1431     </para>
1432   </listitem>
1433 </itemizedlist>
1434 </para>
1435
1436 <sect1><title>Why <literal>C++</literal>?</title>
1437
1438 <para>Why did we choose to implement GiNaC in <literal>C++</literal>
1439 instead of <literal>Java</literal> or any other language?
1440 <literal>C++</literal> is not perfect: type checking is not strict
1441 (casting is possible), separation between interface and implementation
1442 is not complete, object oriented design is not enforced.  The main
1443 reason is the often scolded feature of operator overloading in
1444 <literal>C++</literal>. While it may be true that operating on classes
1445 with a <literal>+</literal> operator is rarely meaningful, it is
1446 perfectly suited for algebraic expressions. Writing 3x+5y as
1447 <literal>3*x+5*y</literal> instead of
1448 <literal>x.times(3).plus(y.times(5))</literal> looks much more
1449 natural. Furthermore, the main developers are more familiar with
1450 <literal>C++</literal> than with any other programming
1451 language.</para>
1452
1453 </chapter>
1454
1455
1456 <bibliography>
1457 <bibliodiv>
1458
1459 <biblioentry>
1460   <bookbiblio>
1461     <title>ISO/IEC 14882:1998</title>
1462     <subtitle>Programming Languages: C++</subtitle>
1463   </bookbiblio>
1464 </biblioentry>
1465
1466 <bibliomixed>
1467   <title>CLN: A Class Library for Numbers</title>
1468   <authorgroup>
1469     <author>
1470       <firstname>Bruno</firstname><surname>Haible</surname>
1471       <affiliation><address><email>haible@ilog.fr</email></address></affiliation>
1472     </author>
1473   </authorgroup>
1474 </bibliomixed>
1475
1476 <biblioentry>
1477   <bookbiblio>
1478     <title>The C++ Programming Language</title>
1479     <authorgroup><author><firstname>Bjarne</firstname><surname>Stroustrup</surname></author></authorgroup>
1480     <edition>3</edition>
1481     <isbn>0-201-88954-4</isbn>
1482     <publisher><publishername>Addison Wesley</publishername></publisher>
1483   </bookbiblio>
1484 </biblioentry>
1485
1486 <biblioentry>
1487   <bookbiblio>
1488     <title>Algorithms for Computer Algebra</title>
1489     <authorgroup>
1490       <author><firstname>Keith</firstname><othername>O.</othername><surname>Geddes</surname></author>
1491       <author><firstname>Stephen</firstname><othername>R.</othername><surname>Czapor</surname></author>
1492       <author><firstname>George</firstname><surname>Labahn</surname></author>
1493     </authorgroup>
1494     <isbn>0-7923-9259-0</isbn>
1495     <pubdate>1992</pubdate>
1496     <publisher>
1497       <publishername>Kluwer Academic Publishers</publishername>
1498       <address><city>Norwell</city>, <state>Massachusetts</state></address>
1499     </publisher>
1500   </bookbiblio>
1501 </biblioentry>
1502
1503 <biblioentry>
1504   <bookbiblio>
1505     <title>Computer Algebra</title>
1506     <subtitle>Systems and Algorithms for Algebraic Computation</subtitle>
1507     <authorgroup>
1508       <author><firstname>J.</firstname><othername>H.</othername><surname>Davenport</surname></author>
1509       <author><firstname>Y.</firstname><surname>Siret</surname></author>
1510       <author><firstname>E.</firstname><surname>Tournier</surname></author>
1511     </authorgroup>
1512     <isbn>0-12-204230-1</isbn>
1513     <pubdate>1988</pubdate>
1514     <publisher>
1515       <publishername>Academic Press</publishername>
1516       <address><city>London</city></address>
1517     </publisher>
1518   </bookbiblio>
1519 </biblioentry>
1520
1521 </bibliodiv>
1522 </bibliography>
1523
1524
1525 <index id="index">
1526 <title>Index</title>
1527
1528 <indexentry>
1529   <primaryie linkends="CLN-main">CLN</primaryie>
1530   <secondaryie linkends="ind123">obtaining</secondaryie>
1531 </indexentry>
1532
1533 <indexentry id="ind-gcd">
1534   <primaryie linkends="gcd-main">gcd</primaryie>
1535 </indexentry>
1536
1537 <indexentry>
1538   <primaryie>lcm</primaryie>
1539   <seeie linkend="ind-gcd">gcd</seeie>
1540 </indexentry>
1541
1542 </index>
1543
1544 </book>