introduce gcd_pf_mul: gcd helper to handle partially factored expressions.

GiNaC tries to avoid expanding expressions while computing GCDs and applies
a number of heuristics. Usually this improves performance, but in some cases
it doesn't. Allow user to switch off heuristics.

Part 3:

Move the code handling products from gcd() into a separate function. This
is *really* only code move, everything else should be considered a bug.

introduce gcd_pf_pow: gcd helper to handle partially factored expressions.

GiNaC tries to avoid expanding expressions while computing GCDs and applies
a number of heuristics. Usually this improves performance, but in some cases
it doesn't. Allow user to switch off heuristics.

Part 2:

Move the code handling powers from gcd() into a separate function. This
is *really* only code move, everything else should be considered a bug.

gcd: allow user to override (some of) heuristics.

GiNaC tries to avoid expanding expressions while computing GCDs and applies
a number of heuristics. Usually this improves performance, but in some cases
it doesn't. Allow user to switch off heuristics.

Part 1:

* add new (optional) argument to gcd() to control its behaviour.
* introduce gcd_options structure.

N.B. No actual code changes so far, the actual handling of newly introduced
options is the subject of further patches.

inifscn_nstdsums: make functions handling Li/G transformations reentrant.

Explicitly pass the dummy symbols instead of using a global variable.
As a side effect, the code is more clear now (that's a bit subjective, but
anyway).

Bail out if both autogen and autogen'erated file(s) are missing.

This makes the error message(s) more helpful.

Faster, better (recursive descent) expression parser.

Ouch, it fails to compile. Here is a correct version:

From: Alexei Sheplyakov <varg@theor.jinr.ru>
Date: Tue, 19 Aug 2008 21:50:03 +0400
Subject: [PATCH] Faster, better (recursive descent) expression parser.

bison generated parser has a number of problems:

1. Bad performance. Parsing a sum seems to be O(N^{2 + a}) (a > 0) [1].
   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).
3. Parser is not reentrant (bison *can* produce reentrant parsers, but that
   won't solve other problems).
4. Parser is difficult to extend.

Hence the new parser.

Features:

1. Parsing large sums and products is O(N).
2. Parser is reentrant (well, almost).
3. It's possible to insert (shell style) comments inside the expressions.
4. matrices, lists, FAIL are NOT handled. Yes, this *is* a feature :-)

Limitations:

1. Error handling is a bit terse: on error exception is thrown, and that's it.
2. Binary, octal, and hexadecimal numbers can not be parsed (yet).
3. Tensors, noncommutative products, etc. can not be parsed.

Other notes:

1. ex ctor still uses the old parser.
2. ginsh still uses the old parser.

[1] Mesured by this script (requires gnuplot):

make_expression_string ()
{
printf "1 + x"
local n=2
while test $n -le $1; do
printf " + %s*x^%s" $n $n
n=$(expr $n + 1)
done
}

single_test ()
{
printf "$1 \t"
( printf "time("; make_expression_string $1; printf ");" ) | \
ginsh | sed -e 's/s$//'
}

benchmark ()
{
local N=$1
while test $N -le $2; do
single_test $N
N=$(expr $N \* 2)
done

}

gnuplot_header ()
{
  echo "set logscale xy"
echo "set xlabel 'degree (# of terms)'"
echo "set ylabel 'time, sec.'"
echo "set xrange [${1}:${2}]"
echo "plot '-' using 1:2 with lines title '1+x+2*x^2+...+n*x^n'"
}

gnuplot_footer ()
{
echo "e"
}

benchmark_and_plot ()
{
( gnuplot_header $1 $2
  benchmark $1 $2 | tee $3.txt
  gnuplot_footer ) | \
gnuplot -persist '-'
}

N_ini=${1:-1024}
N_fin=${2:-32768}
out_base=${3:-parser_benchmark}

benchmark_and_plot $N_ini $N_fin $out_base

Daily bugfix in the polynomial factorization (code didn't catch polynomial "x"
and cln::sqrt conversion was buggy).

Fixed bug in the Q matrix calculation and the univariate factorization function.

Fixed bug in modular square-free factorization.

Added polynomial factorization (univariate case).

Added polynomial factorization (univariate case).

Any complex number can be (un)archived properly.

A complex number can have an exact real part and inexact (floating point)
imaginary part, and vice a versa. Handle these cases properly in the archiving
code instead of bailing out with a bizzare error message.

Thanks to Chris Bouchard for reporting the bug.

NOTE: this fix changes the format of GiNaC archives, so formally it breaks
the binary compatibility. However, "mixed" complex numbers (i.e.  ones with
exact real part and inexact imaginary part) can not be archived with previous
versions of GiNaC, so there's nothing to break.

define lgamma and tgamma taking cl_N as an argument.

The actual code is the same. These functions are OK since cl_N is not
automatically converted to numeric any more.

Implicit conversion from cl_N to numeric considered harmful.

Finally, mark the numeric(const cl_N&) ctor as explicit.
This allows one to mix the code using GiNaC and CLN, i.e.

cl_N x, y;
// initialize them
cl_N z = sin(x) +  y*exp(y);
symbol a("a");
ex e = exp(a);

bernoulli, fibonacci, iquo: explicitly convert return values to numeric.

Implicit conversion from cl_N to numeric considered harmful, part 6.

tgamma, lgamma: convert to take cl_N as an argument; provide wrappers for GiNaC::numeric

Implicit conversion from cl_N to numeric considered harmful, part 5.

Li2, zeta, sqrt, abs, gcd, etc.: explicitly convert return value to numeric.

Implicit conversion from cl_N to numeric considered harmful, part 4.

elementary functions: explicitly convert return values from cl_N to numeric.

Implicit conversion from cl_N to numeric considered harmful, part 3.

inifcns_nstdsums.cpp: Lin_numeric takes cl_N as an argument instead of numeric.

Implicit conversion from cl_N to numeric considered harmful, part 2.

inifcns_nstdsums.cpp: S_num takes cl_N as an argument instead of numeric.

Implicit conversion from cl_N to numeric considered harmful.

Using GiNaC::numeric for numerical computations incurs significant
overhead, so one might want to do these computations using proper CLN
types. Unfortunately, it's not easy due to automatic conversion from
cln::cl_N to GiNaC::numeric. Here is a simple example:

cl_N x, y;
// initialize them
return sin(x) +  y*exp(y);

The compiler complains about ambigously overloaded of functions, i.e.
cl_N cln::sin(const cl_N&) versus numeric GiNaC::sin(const numeric&).

Hence, I propose to disable *implicit* conversion from cl_N to numeric
(this can be done by marking the numeric ctor as `explicit').

However, this change happens to be a bit nontrivial, because that evil
conversion is used in GiNaC itself. So, I decided to rewrite those fragments
of code.

documentation: it is get_dim(), not get_dimension()

This was misdocumented ever since GiNaC-0.8.0.

clifford_unit: fix possible bugs due to wrong operator[!=]= usage.

Removed left-over debugging line.

Make the behaviour of class function more consistent with respect to
ncmul::eval(). [V.Kisil]

Improve heur_gcd() so it can handle rational polynomials, and add a test case.

Previously heur_gcd() worked only with integer polynomials, and did not check
if the inputs are indeed integer polynomials. That lead to an endless loop or
a miscomputed gcd.

[A.Sheplyakov]

Fixed bug in mLi summation causing premature drop-out and made Nielsen polylog
invalidate its lookup tables if precision has been changed.

Added legacy tests for zeta and multiple polylog.

Check for fixed bug in multiple polylogs.

Fixed bugs found by Jianqiang Zhao.

Adjust for GiNaC 1.5.

Merge commit 'origin/master'

Fixed make distcheck issues.

Update debian/changelog in anticipation of release.

In reality, I'm testing the post-receive hook.

Merge git://www.ginac.de/ginac

Small improvement to VPATH fix.

Fixed info-generation problems with VPATH builds.

Update debian/ files.

Use the files that were uploaded with GiNaC 1.4.1 in Debian.

Happy new year!

Updated all copyright notices.

move rotate_left() function away from the public header.

INSTALL: libreadline is not mandatory; ginsh builds just fine without it.

update the compiler info; tell users to avoid GCC 4.3.0

symbol.cpp: shut up useless warnings

../../sw/ginac/ginac/symbol.h: In constructor 'GiNaC::symbol::symbol()':
../../sw/ginac/ginac/symbol.h:112: warning: 'GiNaC::symbol::ret_type_tinfo' will be initialized after
../../sw/ginac/ginac/symbol.h:110: warning:   'unsigned int GiNaC::symbol::domain'
../../sw/ginac/ginac/symbol.cpp:47: warning:   when initialized here
../../sw/ginac/ginac/symbol.h: In constructor 'GiNaC::symbol::symbol(const std::string&, unsigned int)':
../../sw/ginac/ginac/symbol.h:112: warning: 'GiNaC::symbol::ret_type_tinfo' will be initialized after
../../sw/ginac/ginac/symbol.h:110: warning:   'unsigned int GiNaC::symbol::domain'
../../sw/ginac/ginac/symbol.cpp:75: warning:   when initialized here
../../sw/ginac/ginac/symbol.h: In constructor 'GiNaC::symbol::symbol(const std::string&, unsigned int, const void*, unsigned int)':

The warnings are a bit silly, but they can hide more useful ones.

check: indicate the test failures with non-zero exit code; split test programs.

IMNSHO parsing the output of test programs in order to check if the
tests passed is a bad idea (and it causes *real* problems, see e.g.
http://www.ginac.de/pipermail/ginac-list/2008-February/001345.html).
It's much simpler and cleaner to indicate the failure in a genuine
*NIX way: exit with nonzero code.

* Version 1.5.

* Improved lsolve() of systems containing non-numeric coefficients.

kill spurious comma in flags.h

check/*_memleak.cpp: fix botched CVS commit[s].

Improve instructions for installing GiNaC from CVS.

* prerequisites: mention libtool, flex, and bison.
* installation: required software should be installed BEFORE generating
  the `configure' script.

* Fix GCC 4.3 compilation issue by removing storage class of function coerce specializations [C++98 7.1.1-1].

Fixed memory leak program.

* Fixed module loading bug (occured if . was not in the library path).

* Fixed broken preprocessor instruction [Sheplyakov].

* Fixed memory leak in ginac_yylex() [Sheplyakov].

Added small program that exhibits the memory leak in the ginac_yylex() [Sheplyakov].

* Deleted bogus try -- catch block in the ex::series() [Sheplyakov].

* Added check for memory leak in {mul,power}::eval [Sheplyakov].

* Fixed macro checking for version of libreadline (Mac OS X) [Sheplyakov].

* Fix optimization opportunities missed by Alexei's patch.

- Do not bother to rename indices if object has no indices at all [Sheplyakov].

- This helps mul::expand() and friends to recognize objects which have
no indices at all [Sheplyakov].

- Apparently, in ~ 30% of calls to mul::expand the expression is monomial.
Expanding monomials should be done as fast as possible [Sheplyakov].

- Partially solves performance regression in expand(), gcd(), etc [Sheplyakov].

- info(info_flags::has_indices) now works for sums and products. It
returns true if the expression has indices (no matter dummy or free),
and false otherwise [Sheplyakov].

Improved CLN output [Sheplyakov].

Added example for mystring class [Sheplyakov].

Removed reference to autogen.sh [Sheplyakov]

* Adjust to files used for rolling Debian's 1.4.0-1 GiNaC packages.

Put entire GiNaC documentation into @dircategory 'Mathematics' for info.

Added missing example source.

Added CLEANFILES.

Hide failure due to term reordering.

Preparing for release.

Added compiler.h

File added [A.Sheplyakov]

Added changes.

input_parser accepts also pow() [A.Sheplyakov]

Converting terms into primitive polynomials optimized [A.Sheplyakov]

info_flags::expanded added [A.Sheplyakov]

lst_to_clifford() and clifford_to_lst() can handle pseudo-vector representation
now [V.Kisil].

Removed texinfo.tex

* Fix GCC-4.3 compilation issue.

- Fixed typos and layout problems.
- Fixed missing tex in html output.
- Changed text to be compatible with new tinfo system.

Added missing is_negative() inline function.

Updating all changes.

Improved clifford_moebius_map() [V.Kisil]

Fixed error in examples for match.

* Analytic continuation for atan2(y,x) for complex y and x.

Clifford units now honor representation labels.

Additional transformations for mul and power [Sheplyakov].

Correct csrc output for fderivative [Grabner].

Applied print_csrc patch [Grabner/Sheplyakov]

Patch by Stefan Weinzierl that fixes a bug in series expansion.

* Fix compilation issues with prereleases of GCC 4.3, at least in theory.
  See <http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=417199>.

* Use pkg-config for detecting CLN, advertise it in the manual and drop
  ginac-config and ginac.m4. [Alexei Sheplyakov]

Patch by Alexei.

Alexeis patch for faster Lanczos coefficient calculation.

Improved handling of convergence transformationis for Li/G (fixes problems with certain H() evaluations).

Alexeis patches for documentation and correct degree of 1/symbol.

Faster archiving by adding a map from strings to idices in the atoms vector.

Fixed bug in taking real and imaginary part.