[PATCH 1/2] extract_integer_content: check for rational numbers properly.

Commit 3d09388a (titled as `[bugfix] chinrem_gcd: handle polynomials over
rationals properly.') broke extract_integer_content: now it always returns 1.
The check for rational `integer_contnent' introduced by that commit is wrong
(since integers is a subset of rationals). Rewrite the check proprerly.
(cherry picked from commit f0fb303711b4334ce59f7da63bfa7cb49f46265f)

[bugfix] chinrem_gcd: handle polynomials over rationals properly.

* extract_integer_content():
  integer_content() can also return a rational number, e.g if the expression
  is a polynomial over rationals (in this case expr/content is polynomial
  over integers with integer content being 1). Therefore check if
  integer_content() is really an integer (and if it's not just return 1,
  GCD for polynomials over a field is defined up to arbitrary element of
  the field).

  This fixes possible segfault when computing GCD of polynomials over
  rationals (this is not theoretical, see the added test case).

Thanks to Ernst Moritz Hahn for reporting this bug.
(cherry picked from commit 3d09388a8ea144a19949c216fae43ccba92e47aa)

power::series(): handle someg (trivial) singularities of the exponent...

... so GiNaC can expand expressions like

cos(x)^(sin(x)/x) // (x -> 0)
(1 + x)^(1/x) // x -> 0

and so on.

[Reported by Camille Gillot.]
(cherry picked from commit 079c558d4f9758cd2777a2808a02d64cb1f70c8e)

mul: algebraic_subs_mul(), has(): don't write beyond the end of array

algebraic_match_mul_with_mul() iterates over operands of mul, that is

for (size_t i=0; i<e.nops(); ++i)

However, the size of arrays (`vectors' in STL speak) passed to this
function is seq.size(), which is nops() - 1 for any mul object. Thus
algebraic_match_mul_with_mul() accesses beyond the arrays limit. Usually
it's not a problem, since any reasonable implementation of std::vector<bool>
packs booleans into ints (or longs). However, some STL implementations
(in particular, the one shipped with msvc) are more picky, and access
beyond the vector<bool> limits results in a segfault. Therefore let's
play safe and allocate proper number of elements (that is, nops()) for
those arrays (subsed and currsubsed).
(cherry picked from commit cbb93fadabbd56ba006902967b15b2b2aebb037c)

Avoid infinite loop when unarchiving realsymbol and possymbol.

symbol::read_archive(): explicitly set status_flags::evaluated (and
status_flags::expanded) on object being unarchived. These flags get
reset by basic::operator=(const basic&) for realsymbol and possymbol,
and nothing sets (except symbol ctor), so automatic evaluation never
terminates (or rather, terminates due to a stack overflow). Therefore
it's necessary need to set status_flags::evaluated explicitly.

Thanks to Markus Fröb for a bugreport and a test case.
(cherry picked from commit e99d0d58c1bbaa8ee73e4a90a90aa1086f2f813d)

Make sure add::eval() collects all numeric terms.

Apparently, add::eval() assumed that none of the elements of its epvector
has a numeric rest. However, nothing guarantees that -- in particular
evalchildren() doesn't (and actually cannot) do so. Since there are many
places where a new add is constructed directly from an epvector, enforcing
this doesn't make sense either. One example where it did fail was found by
Burgin Erocal: real_part(1+2*(sqrt(2)+1)*(sqrt(2)-1)) returned 1+2*1, not 3.

Thanks to Burcin Erocal for reporting this bug.
(cherry picked from commit e08cda1854bdb82f6706ec269233577690ae00e4)

Be more careful about final top-level substitution.

Substituting x==log(x) in exp(x) erroneously returned log(x) because of a
final subst(x==log(x)) after having eval'ed exp(log(x)) -> x. This final
substitution is wrong in the general case. On the other hand, the intent
is to syntactically substitute functions of a given kind etc. This patch
suppresses the final top-level substitution unless the intermediate result
is a container.

Thanks to Burcin Erocal for reporting this bug (originally described by
Kees van Schaik on sage-support@googlegroops.com).

Fix autoconf warning about AC_INIT use.

Apparently, autoconf doesn't like the angle brackets in the bug-report
argument any more. It comlains "not a literal: <ginac-list@ginac.de>".
So let's remove it. And while at it, also provide tarname and url
arguments.

power::eval(): fix several memory leaks

While working on fsolve bug I've noticed the following in valgrind log:

==17455== 136 (56 direct, 80 indirect) bytes in 1 blocks are definitely lost in loss record 16 of 19
==17455==    at 0x4C249C7: operator new(unsigned long) (vg_replace_malloc.c:220)
==17455==    by 0x516CA70: GiNaC::power::eval(int) const (power.cpp:540)
==17455==    by 0x4FC1E39: GiNaC::ex::construct_from_basic(GiNaC::basic const&) (ex.cpp:310)
==17455==    by 0x406FBF: main (ex.h:255)

Heap allocated objects definitely need the status_flags::dyncallocated flag.
(cherry picked from commit 5f896fa7f59bbce727e4bba23df9c4bbdbb55c29)

fsolve: avoid useless numerical evaluation of the function

Don't compute f(x) if new x is outside of the interval. We don't need that
value anyway, and the function might be difficult to compute numerically or
even ill defined outside the interval.

As a result fsolve is able to find root(s) of some weird functions.
For example

fsolve((1/(sqrt(2*Pi)))*integral(t, 0, x, exp(-1/2*t^2)) == 0.5, x, 0, 100)

actually works now.
(cherry picked from commit beeb0818e9cdb1b5de0ba2754286ad7bb2a9d032)

integral::evalf(): don't attempt to ignore problems.

Don't ignore exceptions thrown by numerical integration routine.
In general, the code like this

try {
// blah-blah
} catch (std::exception& err) { }

is just plain evil. Case in the point:

fsolve((1/(sqrt(2*Pi)))*integral(t,0,x,exp(-1/2*t^2))==0.5,x,0,100)
(cherry picked from commit 515171f0bcd42099c266713c3d605cd92cedd2e2)

fsolve: check if evalf() return value is actually a number.

Fixes the segfault triggered by

fsolve((1/(sqrt(2*Pi)))*integral(t,0,x,exp(-1/2*t^2))==0.5,x,0,100)

In general, ex_to is unsafe, and should be used only after proper checks.
evalf() may return non-numeric expression for various reasons (bad
convergence, floating point over- or underflow, out of memory, etc).
So let's add missing checks.

Thanks to Ernst Moritz Hahn for a bug report.
(cherry picked from commit 9993a7aac97abf383624fc5dae4beecb29531fbd)

Preparing for release 1.5.8.

Removed trailing spaces.
(cherry picked from commit dbde7117e88ba61597d6fee18615fe396c291a87)

Texinfo interprets @strong{Note...} as a cross reference and gives a
warning about it. Changed the text to avoid this.
(cherry picked from commit 7769ce49235ed6510785baa0a29801e3a59b563e)

Parser: handle abbreviations as advertized in the manual.

The following example from the tutorial

GiNaC::symbol x, y;
GiNaC::symtab table;
table["x"] = x+log(y)+1;
GiNaC::parser reader(table);
GiNaC::ex e = reader("5*x3 - x2");

fails with the following exception:

terminate called after throwing an instance of 'std::invalid_argument'
what(): find_or_insert_symbol: name "x" does not correspond to a symbol

Remove silly checks from find_or_insert_symbol, and fix its return value
(should be ex, not symbol).

Be more careful with conjugate(f(x)) -> f(conjugate(x)).

That identity is correct for holomorphic functions, but we have to be
careful with some functions not being holomorphic everywhere. On branch
cuts, it is wrong. For a discussion, see:
<http://www.ginac.de/pipermail/ginac-list/2010-April/001601.html>.

This patch changes the default behavior of user-defined functions. From
now on, a user-defined conjugate_func must be registered, in order to
evaluate conjugate(f(x)) -> f(conjugate(x)). This patch also adds such
functions for most initially known functions.

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.

Preparing for release 1.5.7.

Products (class mul) now answer correctly to info_flags::negative and
info_flags::negint.
(cherry picked from commit 8a30acc990818792ec4e8f8f4d48f5dd8286dbed)

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.

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.
(cherry picked from commit 9e13d46552bb7852399867b9eb355732b9ded59e)

Copyright goes 2010.
(cherry picked from commit 95ede03f00106be5fb087d76c86ca5c27edb9122)

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.
(cherry picked from commit 6afbb9793e359cf388462c471ea256a6662b0cd4)

Preparing for release 1.5.6.

Use C style cast when converting void* into function pointer.

Building GiNaC 1.5.5 with GCC 3.4 fails with the following error:

libtool: compile:  ccache g++-3.4 -DHAVE_CONFIG_H -I. -I../../ginac -I../config -I/home/pc7135/varg/target/x86_64-linux-gnu/include -O2 -g -Wall -pipe -MT builtin_fcns.lo -MD -MP -MF .deps/builtin_fcns.Tpo -c ../../ginac/parser/builtin_fcns.cpp  -fPIC -DPIC -o .libs/builtin_fcns.o
../../ginac/parser/builtin_fcns.cpp: In function `GiNaC::ex (* GiNaC::encode_serial_as_reader_func(unsigned int))(const GiNaC::exvector&)':
/home/pc7135/varg/tmp/build/GiNaC/build-linux-gcc-3.4/ginac/../../ginac/parser/builtin_fcns.cpp|67| error: ISO C++ forbids casting between pointer-to-function and pointer-to-object
make[2]: *** [builtin_fcns.lo] Error 1

The C++98 standard [expr.reinterpret.cast] does not allow

reinterpret_cast<function_pointer>(void*)
reinterpret_cast<void*>(function_pointer)

But the ability to do so is important for a lot of practical uses. So soon
after the C++98 standard was approved, a language defect report was filed
on this topic, see
http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#195
The result is that compilers will be allowed to support reinterpret_cast
conversions of function pointers to other (pointers) types, and vice a versa.
Such conversions work with *current* compilers (GCC 4.x), but don't work
with older ones, hence this patch.

Install the ginac-excompiler script iff excompiler is supported and enabled.
(cherry picked from commit 25c7a8c09f7db73b48675777aa805e788f2308be)

Preparing for release.

Fix libtool versioning fiasco.

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

Preparing for release.

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]

Merge branch 'ginac_1-5' of ssh://www.ginac.de/srv/git/ginac into ginac_1-5

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]

Moved header includes to source files to avoid polluting the namespace
for library users.

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.

ncmul::eval(): don't write beyond the end of the vector.

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+=.
(cherry picked from commit 59ec13895c97ffd74979a0b811a7571f6de56386)

Added get_builtin_reader() that parses only the builtin GiNaC functions
and pow, sqrt, and power.

Fixed include of stdint.h (parser.cpp needs the header as well).

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]).
(cherry picked from commit 694f839947982f5b12b6c629d5bab522c801630d)

symmetry::calchash(): be careful to not dereference past-the-end iterator.
(cherry picked from commit 526825bcee294cb20e37d8db6d5040ba0f8c428f)

check_parameter_G: fix pontential increment of end().

Incrementing past-the-end iterator is not permitted by the standard, see
[lib.input.iterators].
(cherry picked from commit 49a44f7d55ec0d6686d3c32c7081a07d10c93274)

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).
(cherry picked from commit dda45abd8a2c408f8b3eb7959a10dfb2468ecc3a)

Fix the compliation error *for real* ... and restore performance

Commit 8bf0597dde55e4c94a2ff39f1d8130902e3d7a9b (titled as 'Fixed the parser
such that it can read in user defined classes again.') made the parser a bit
slower, especially if the input contains many terms of user-defined type.
The reason for that is quite simple: we throw and catch an exception every
time we construct an object of user-defined type:

       // dirty hack to distinguish between serial numbers of functions and real
       // pointers.
       GiNaC::function* f = NULL;
       try {
               unsigned serial = (unsigned)(unsigned long)(void *)(reader->second);
               f = new GiNaC::function(serial, args);
       }
       catch ( std::runtime_error ) {
               if ( f ) delete f;
               ex ret = reader->second(args);
               return ret;
       }

Fortunately functions are aligned and we can use much more efficient
technique to distinguish between serial and pointers to functions.

Fix the compliation error *for real*

Fixed memory leak.

Fixed the fix in commit f059ebe117d15292e0d262e6e8e232e835c7e33c.

Fixed dirty hack in parser to distinguish between serial numbers and pointers.

Fixed the parser such that it can read in user defined classes again.
Fixed default reader to parse also pow, sqrt and power.

Fixed cast that caused compile error on 64bit machines.

Preparing for release 1.5.3.

Allow underscores in identifiers.
(cherry picked from commit 619879b5bd86a99334affe1f05d17616cc2c1898)

Allow user defined functions to be parsed.

This patch is an ugly hack that does the same as the commit
f38cbcd651246fb5c1294705d29399f3cbfddaf5
but without changing the ABI (so it can be used in ginac_1-5).

Preparing for release 1.5.2.

Fixed manual to correctly explain return_type_tinfo().
(cherry picked from commit feed241b95f7dbd6294795b4afc2bcae41880c31)

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.

Repairing the preparing of the release.

Preparing for release.

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.