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