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