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