Fix dangerous iterator use.

This was detected by cppcheck and reported by Martin Ettl <ettl.martin@gmx.de>.

pgcd(), chinrem_gcd(): use appropriate definition of the degree.

Effect: fixes (rare) GCD miscalculation.

pgcd() treats polynomials Z_p[x_0, ..., x_n] as R[x_0, ..., x_{n - 1}], where
R = Z_p[x_n]. Therefore one should use correct definition of the degree
(i.e. compute it w.r.t. x_0, ..., x_{n-1}, but NOT w.r.t. x_n!).

One should use appropriate definition of degree (that is, w.r.t.  x_0, ..., x_n)
in chinrem_gcd() too.

Thanks to Aless Lasaruk for a bug report.

Added `degree_vector' utility function.

It's a generalization of degree(expr, var) for multivariate polynomials.

primpart_content: correctly handle monomials.

Impact: fixes (rare) incorrect gcd calculation and (potential) segfault.

Thanks to Aless Lasaruk for a bug report.

pgcd(): avoid infinite loop if the first GCD candidate coincides with GCD

136 if (H_lcoeff.is_equal(lc_gcd)) {
137 if ((Hprev-H).expand().smod(pn).is_zero()) // (*)
138 continue;

The check (*) can result in infinite loop if the (very) first GCD candidate
gives the correct GCD: any subsequent iterations give the same result, so
Hprev and H will be equal (hence the infinite loop). That check is not very
useful (AFAIR I was trying to avoid extra division checks), so let's remove it.

Fix URL of CODA.

Fix memory leak in excompiler due to use of wrong operator delete.

This was reported by Martin Ettl <ettl.martin@gmx.de>.

Explicit function disambiguation.

This is necessary for compilers where the hyperbolic and the tgamma function
templates are pulled in from <cmath> and compete with GiNaC's function
templates. GCC 4.4 and 4.5 need this, when compiling with -std=cxx0x.

Fix weird ctor invocation syntax.

This patch is required for GCC-4.5.

Products (class mul) now answer correctly to info_flags::negative and
info_flags::negint.

Really fixed the atan2(-Pi, 0) bug.

The problem was that atan2_eval assumed that if y is real and not
positive, it must be negative. But this neglects the fact that in
symbolic compution it may just not be possible to determine the
sign. Now, the expression is returned as it is. Ugly, but correct.

Merge branch 'master' of ssh://www.ginac.de/srv/git/ginac

Fixed a bug in atan2. It gave a division by zero error for calls like
atan2(-Pi,0), because arguments like -Pi were not recognized (via
info_flags) as negative but as real nevertheless.

Copyright goes 2010.

Update copyright notice.

pgcd(): detect relatively prime polynomials properly...

... so pgcd() doesn't loop forever any more. Division test does not handle
relatively prime polynomials (because C = 1 divides any polynomial). So we
should stop interpolation (and return gcd of contents) if we got relatively
prime images (we should do that for efficiency reasons too).

Thanks to Jörg Arndt for a bug report.

Install the ginac-excompiler script iff excompiler is supported and enabled.

Fix libtool versioning fiasco.

Fix f2f67dde5c9caca, which caused the soname to be bumped too frequently.

Add mul::info() and add::info() support for numeric info_flags.

This way, GiNaC knows that the sum or product of a number of positive
expressions is again a positive expression. [by Vladimir Kisil]

Output LaTeX-symbols using \mathrm, instead of \mbox.

Using \mathrm improves printing in complex formulae.
One reason is that it scales in fractions. [by Vladimir Kisil]

Remove debian/ directory.

The lifecycle of the Debian packaging files is better maintained in
the Debian pool's diff file. Removing these files makes the life of
the GiNaC releaser easier.

Properly document how to deal with libtool versioning.

The old description was referring to ginac_lt_age which should always
stay 0, because we promised to mark incompatible binary interfaces by
bumping ginac_minor_version (or even ginac_major_version). Let's get
rid of ginac_lt_age.

modular_matrix: don't use STL iterators in {mul, sub}_col and friends.

Not using STL iterators makes the code simpler and cleaner. Also we don't
have to argue whether the standard ([lib.random.access.iterators]) imposes
any pre/post-condictions on operator+=.

shaker_sort, permutation_sign: fix invalid use of STL iterators.

According to the standard incrementing end(), and decrementing begin()
are ill-defined operations (see [lib.forward.iterators],
[lib.bidirectional.iterators]).

symmetry::calchash(): be careful to not dereference past-the-end iterator.

check_parameter_G: fix pontential increment of end().

Incrementing past-the-end iterator is not permitted by the standard, see
[lib.input.iterators].

G_eval: fix incorrect use of STL iterator.

According to [lib.bidirectional.iterators] it's not OK to decrement
an iterator pointing to the beginning of the sequence. Fortunately random
access iterators provided by (current versions of) gcc/libstdc++ don't have
this silly limitation, so the code which works with pointers works with
iterators without any changes at all. However,
 - there's no guarantee that the current behavior won't change in the future
 - some non-GNU compilers are not that smart (i.e. the program segfaults
   upon when decrementing beginning-of-the-sequence iterator).

Allow underscores in identifiers.

Changed the parser such that it understands all defined functions
including the user defined ones.

To this end a method has been added to class function to allow the
modified get_default_reader() function to build up a complete prototype
table. The autogen tool is no longer required.

Fixed manual to correctly explain return_type_tinfo().

Raised required version of CLN to 1.2.2.

Added include for cstdio header.
gcc 4.0 does not include cstdio as part of other headers like string
anymore. As a result, gcc 4.0 complained about EOF being undefined.

calchash(): work around broken RTTI.

Due to the strange (although permitted by the standard) behaviour of C++
RTTI on woe32 calchash() returns different hash values for equal objects.
As a result automatic evaluation gets spectacularly broken:

examining clifford objects.....({1+t,2+x,3+y,4+z}) - ({1+t,2+x,3+y,4+z}) erroneously returned -{1+t,2+x,3+y,4+z}+{1+t,2+x,3+y,4+z} instead of 0
({1+t,2+x,3+y,4+z}) - ({1+t,2+x,3+y,4+z}) erroneously returned -{1+t,2+x,3+y,4+z}+{1+t,2+x,3+y,4+z} instead of 0
.({1+t,2+x,3+y,4+z}) - ({1+t,2+x,3+y,4+z}) erroneously returned -{1+t,2+x,3+y,4+z}+{1+t,2+x,3+y,4+z} instead of 0
({1+t,2+x,3+y,4+z}) - ({1+t,2+x,3+y,4+z}) erroneously returned {1+t,2+x,3+y,4+z}-{1+t,2+x,3+y,4+z} instead of 0
[skipped]
.......FAIL: exam_clifford.exe

This patch works around `features' of woe32 RTTI, so calchash() works
properly.

Fix compilation failure due to (template) operator- defined in factor.cpp

GiNaC 1.5.0 fails to compile with g++ 3.4.
The fix is simple: declare (and define) operator- (and operator+) only
for (univariate) polynomials.

Univariate GCD timing: use sr_gcd when appropriate.

The benchmark consists of two parts:
1) timing of different GCD calculation methods (i.e. subresultant PRS,
   heuristic, chinese remaindering).
2) timing of different implementations of the same method. The purpose
   is to find out how (in)efficient GiNaC::ex is as a representation
   of (univariate) polynomials (as a side note, the result is a bit
   depressing -- using coefficient vector instead of GiNaC:ex makes
   GCD calculation 50x -- 1000x faster).

Now GiNaC uses modular (chinese remaindering) GCD by default, so part 2)
got broken, i.e. instead of (intended) timings

a) (heuristic, GiNaC::ex) versus (heuristic, coefficient vector)
b) (PRS, GiNaC::ex) versus (PRS, coefficient vector)

one gets

a') (heuristic, GiNaC::ex) versus (heuristic, coefficient vector)
b') (chinese remaindering, GiNaC::ex) versus (PRS, coefficient vector)

Set the gcd_options::use_sr_gcd to restore the meaning of the benchmark.

Note: this patch does not affect the library proper.

Polished NEWS a little bit.

Added release date.

Adjusted NEWS and INSTALL documentation.

Missed to change one date in function.pl.

Changed name of debugging macro (to avoid warning cause by multiple definition).

Fixed returning of test result (++result was +result).

Prettified source code.

- Added copyright and GPL licencing to new files.
- Increased year to 2009.
- Changed guarding macros in header to uniform pattern without leading or
  trailing __ (double underscores).
- Put includes of system wide header consistently below own includes (help
  a tiny bit to clarify dependencies).

Fix chinese_remainder() so modular GCD actually works.

Automake now needs to be version >=1.8. Older versions like 1.7.9 do not create
the directory m4 in a VPATH build.

Renamed files *.tcc and *.hpp to *.h.

Fixed compile errors introduced in previous commit
45b1e47372090352ac5af655b32473df2abab23b.

Implement modular multivariate GCD (based on chinese remaindering algorithm).

Both algorithm and implementation are a bit inefficient:

* algorithm does not make use of sparseness of inputs (and most of
  multivariate polynomials are quite sparse)
* GiNaC's expressions are essentially immutable. Thus some simple
  operations (i.e. multiplying a polynomial by an element of the base ring)
  are prohibitively expensive.
* All numbers (i.e. GiNaC::numeric objects) are heap allocated.

Still it's much faster (~5x on bivariate polynomials, ~100x on 3-variate
ones) than (subresultant) PRS algorithm, so gcd() uses modular algorithm
by default.

Improve (fix?) smod: now it really converts into symmetric representation...

... instead of clumsy convention inspirited by some proprietary CAS.

Fix copy-paste error in GINACLIB_MICRO_VERSION.

Fixed bug in binomial(). binomial(n,0) erroneously returned 0.

Small fixes to avoid compile warnings (-Wall).

Fixed bug in multivariate factorization. Fractional numerical content was not
extracted and led to a not so finite running behavior. Added new checks for that
bug.

Added static keywords to hide debugging output operators.

Added new items.

[PATCH] [build] Simplify generation of ginac/version.h

[PATCH] Fix GiNaC library version information.

The libtool naming scheme cannot guarantee that on all systems, the numbering
is consecutive. It only guarantees that it is increasing. This doesn't matter,
though: there is not incurred cost for numbers that are omitted, except for
shrinking the available space of leftover numbers. Not something we need to
worry about yet.  ;-)  On the other hand, tricks which we were using to make
version numbers consecutive on GNU/Linux break versioning on other OSes.

Fixed a problem in polynomial divide by deactivating a recursion that lead to a
significant slowdown in sqrfree() and sometimes to a infinite loop.

Added section about factor(). Made appropriate changes at other places.

Added many comments.

Fixed lots of bugs in factor_multivariate().

factor_univariate() takes now the content of the polynomial into accout when
choosing a prime. It also returns the chosen prime. This supports the
factor_multivariate() code.

Polynomials are expanded before calling factor_sqrfree(). This avoids problems
with some input polynomials.

Added static qualifiers to all hidden functions.

Fixed a bug in squarefree(). Some polynomials were erroneously classified as
square free (e.g. x^prime+1).

Fixed a bug in multivar_diophant() causing  sporadically an infinite loop.

Improved lifting bound code.

Univariate lifting can now use a cache for the modular factors. At the moment,
this gives no measurable speed gain.

Added modular square free factorization.
Completed distinct degree factorization.
Univariate polynomial factorization uses now upoly.
Merged class Partition and function split into class factor_partition.

Stupid error: did the revert on the wrong branch (master instead of ginac_1-4).

Revert "Revert "[portability] GiNaC::compile_ex works on OpenBSD now.""

This reverts commit a6854a8a0f1e5db722320f5d7ccb9097053500cf.

Revert "[portability] GiNaC::compile_ex works on OpenBSD now."

This reverts commit 375a7aa1f13fa6061c278eb2c2447fd91521b45d.

Univariate Hensel lifting now uses upoly.
Changed q_matrix code.

Equip ginac-examples.texi with directory entry for info.

[portability] GiNaC::compile_ex works on OpenBSD now.

* acinclude.m4: check for dlopen() in libdl and in libc itself.

Thanks to Paul Irofti for a bug report and a suggestion.

[build] Set correct rpath for linking with CLN...

... so users won't get 'error while loading shared libraries: no such file
or directory'. Also embed rpath into pkg-config meta data, so

g++ `pkg-config --cflags --libs ginac` foo.cc

actually works without any additional effort from the user side.

[bugfix] integer_cra: check if arguments contain at least 2 moduli

While at it, also fix exam_cra so it does not produce pointless inputs.

exam_cra: explicitly #include <limits>. This should make g++ 4.3 happy.

Changed debugging facilities in factor.cpp.

Fixed some minor spelling errors.

Changed code from using cl_UP_MI to using umodpoly. The cl_UP_MI interface was
inconvenient to use and caused several very difficult bugs (some were still
unresolved before changing to umodpoly!).

Fixed severe bug in multivariate factorization. The condition that all modular
factors should be relatively prime in the base ring was violated. This caused
the factorization sometimes to go into an infinite loop.

Added code for distinct degree factorization.

tutorial: simplify the instructions on writing extension classes.

Don't mention (un)archiving while describing the `mystring' class
(the minimalistic extension class), so readers have less chances to get
confused.

Don't force every algebraic class to implement archiving/unarchiving.

So people who don't use (un)archiving don't need to bother with it.

tutorial: don't mention custom RTTI any more (as it does not exist).

symbol: make get_domain() a virtual method, remove symbol::domain.

This cuts yet another 4 bytes from GiNaC::symbol. While at it, fix a memory
leak in ginsh.

symbol: don't bother to set TeX name if user did not specified one.

Same for the usual name. As a result we use less memory (and the output
is exactly the same).

symbol: remove return_type_tinfo() and return_type() (shrink symbol by 8 bytes)

Bloating symbol to the state sizeof(symbol) == 64 is not appreciated at all.
If someone needs/wants non-commutative symbols or other fancy stuff, please
derive from class symbol and do whatever you want.

Wipe out remnants of custom RTTI.

Custom RTTI considered harmful, final part.

registered_class_info: use typeid() instead of tinfo_static.

(Custom RTTI considered harmful, part 5).

Since custom RTTI is going to be removed, registered_class_info needs to be
re-organazied. Now tinfo_key is a (const) pointer to std::type_info.

A better return_type_tinfo() mechanism.

return_type_tinfo() is used in order to distingish between non-commutative
objects of different type. However, often it's necessary to distingish
between non-commutative objects of the same type, for example, between
gamma matrices with different representation label. return_type_tinfo()
does not provide any clean way to do that. Hence, introduce return_type_t
type which holds representation label along with type information, and
use it for return_type_tinfo().

calchash(): use type_info::name() instead of tinfo().

Custom RTTI considered harmful, part 4.

The hash value of the object of different types should be different whenever
possible. Hence calcash() needs a unique per type number. Previously we used
tinfo_key for this. typeinfo::name() (a *pointer* to implementation dependent
string) is also unique for each class, so it's just as good as tinfo() is.

indexed::eval: use standard C++ RTTI.

Custom RTTI considered harmful, part 3.

basic, expairseq: use standard C++ RTTI in compare(), is_equal(), match(), etc.

Custom RTTI considered harmful, part 2.

* basic.cpp: use standard C++ RTTI in compare(), is_equal(), operator=(),
  match().
* expairseq.cpp: use standard C++ RTTI in match(), make_flat(),
  construct_from_2_ex().

is_exactly_a: use typeid() to check the type of expression.

Custom RTTI considered harmful, part 1.

Custom run time type information (RTTI) system implemented in GiNaC have
several serious drawbacks, such as

1. It makes writing GiNaC classes unnecessary cumbersome.
2. It wastes sizeof(void *) bytes per object, for small objects like
   symbol, numeric, etc. this overhead is considerable.

It turns out that GiNaC's RTTI is not any faster than the standard one
(at least on GNU/Linux and Solaris with GNU C++ library and compiler).
So, GiNaC RTTI have no reasons to exit any more.

ptr.h: use unsigned int to store reference counts (in order to save memory).

We'll hardly ever get more than 2^32 references to the same object. So using
size_t to store reference count only wastes 4 bytes per object (on 64-bit
architecture). Use unsigned int instead.

Rewritten heuristic and PRS GCD for univariate polynomials, added benchmark.

Using a better data structure for univariate polynomials makes GCD 10 -- 300
times faster (and less memory hungry).

polynomial: introduce a helper function to divide polynomial by ring element.

mod_gcd: naive hack to chose a 'good' prime (to speed up gcd computation).

[bugfix] remainder_in_ring: using exact division is plain wrong.

[bugfix] normalize_in_ring: don't set the leading coefficient to 1.

The coefficient ring is not a field, so the leading coefficient don't
have to be 1.

[trivial] excompiler.cpp: shut up some silly compiler warnings.

GCC warns about 'comparison between signed and unsigned integer expressions'.
In this case such comparison is harmless, but still it's a bit annoying.

Merge branch 'master' of git://ffmssmsc.jinr.ru:443/varg/ginac

Replaced class UniPoly by cl_UP_MI.

- Added options argument to factor(). Added flag factor_options::all that lets
  factor() act on all polynomial subexpressions.
- Added more comments.

Implemented modular GCD algorithm for univariate polynomials.

Wipe out the old (bison/flex generated) parser.

Bison generated parser has a number of problems:

1. Bad performance. Parsing a sum seems to be O(N^{2 + a}) (a > 0).
   For example, parsing a sum (actually, a univariate polynomial) of 32768
   terms takes about 90 sec. on my box, parsing a sum of 10^6 terms takes
   "eternity".
2. The user is expected to provide list of all symbols in the expression.
   Often this is very annoying (and useless), sometimes it is not possible
   at all.
3. Parser is not reentrant (bison *can* produce reentrant parsers, but that
   won't solve other problems).
4. Parser is difficult to extend.

Since the new parser handles almost everything (useful) as the old one, let's
remove the latter.

check: time_parser.cpp: don't run the same benchmark twice.

Since ex(const string&, lst&) ctor uses the new parser now comparing its
performance (and result) with one of direct invocation of the parser is
pointless.

Document the new parser, provide an example.