11 years agoAdded section about factor(). Made appropriate changes at other places.
Jens Vollinga [Fri, 14 Nov 2008 11:00:52 +0000 (12:00 +0100)]
Added section about factor(). Made appropriate changes at other places.

11 years agoAdded many comments.
Jens Vollinga [Thu, 13 Nov 2008 15:36:02 +0000 (16:36 +0100)]
Added many comments.

11 years agoFixed lots of bugs in factor_multivariate().
Jens Vollinga [Thu, 13 Nov 2008 10:13:05 +0000 (11:13 +0100)]
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.

11 years agoFixed a bug in squarefree(). Some polynomials were erroneously classified as
Jens Vollinga [Tue, 11 Nov 2008 09:33:29 +0000 (10:33 +0100)]
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.

11 years agoAdded modular square free factorization.
Jens Vollinga [Mon, 10 Nov 2008 12:38:11 +0000 (13:38 +0100)]
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.

11 years agoStupid error: did the revert on the wrong branch (master instead of ginac_1-4).
Jens Vollinga [Thu, 6 Nov 2008 13:18:01 +0000 (14:18 +0100)]
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.

11 years agoRevert "[portability] GiNaC::compile_ex works on OpenBSD now."
Jens Vollinga [Thu, 6 Nov 2008 13:13:54 +0000 (14:13 +0100)]
Revert "[portability] GiNaC::compile_ex works on OpenBSD now."

This reverts commit 375a7aa1f13fa6061c278eb2c2447fd91521b45d.

11 years agoUnivariate Hensel lifting now uses upoly.
Jens Vollinga [Thu, 6 Nov 2008 13:11:02 +0000 (14:11 +0100)]
Univariate Hensel lifting now uses upoly.
Changed q_matrix code.

11 years agoEquip ginac-examples.texi with directory entry for info.
Paul Irofti [Tue, 4 Nov 2008 14:55:34 +0000 (17:55 +0300)]
Equip ginac-examples.texi with directory entry for info.

11 years ago[portability] GiNaC::compile_ex works on OpenBSD now.
Alexei Sheplyakov [Mon, 3 Nov 2008 16:17:16 +0000 (19:17 +0300)]
[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.

11 years ago[build] Set correct rpath for linking with CLN...
Alexei Sheplyakov [Mon, 3 Nov 2008 14:34:29 +0000 (17:34 +0300)]
[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`

actually works without any additional effort from the user side.

11 years ago[bugfix] integer_cra: check if arguments contain at least 2 moduli
Alexei Sheplyakov [Thu, 23 Oct 2008 13:48:14 +0000 (17:48 +0400)]
[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.

11 years agoexam_cra: explicitly #include <limits>. This should make g++ 4.3 happy.
Alexei Sheplyakov [Tue, 21 Oct 2008 06:09:33 +0000 (10:09 +0400)]
exam_cra: explicitly #include <limits>. This should make g++ 4.3 happy.

11 years agoChanged debugging facilities in factor.cpp.
Jens Vollinga [Wed, 5 Nov 2008 12:56:53 +0000 (13:56 +0100)]
Changed debugging facilities in factor.cpp.

11 years agoFixed some minor spelling errors.
Jens Vollinga [Wed, 5 Nov 2008 10:31:35 +0000 (11:31 +0100)]
Fixed some minor spelling errors.

11 years agoChanged code from using cl_UP_MI to using umodpoly. The cl_UP_MI interface was
Jens Vollinga [Wed, 5 Nov 2008 10:22:19 +0000 (11:22 +0100)]
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.

11 years agoAdded code for distinct degree factorization.
Jens Vollinga [Mon, 3 Nov 2008 14:50:31 +0000 (15:50 +0100)]
Added code for distinct degree factorization.

11 years agotutorial: simplify the instructions on writing extension classes.
Alexei Sheplyakov [Sun, 19 Oct 2008 16:21:33 +0000 (20:21 +0400)]
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

11 years agoDon't force every algebraic class to implement archiving/unarchiving.
Alexei Sheplyakov [Sun, 19 Oct 2008 15:39:30 +0000 (19:39 +0400)]
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.

11 years agotutorial: don't mention custom RTTI any more (as it does not exist).
Alexei Sheplyakov [Fri, 17 Oct 2008 13:57:27 +0000 (17:57 +0400)]
tutorial: don't mention custom RTTI any more (as it does not exist).

11 years agosymbol: make get_domain() a virtual method, remove symbol::domain.
Alexei Sheplyakov [Thu, 16 Oct 2008 11:43:32 +0000 (15:43 +0400)]
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.

11 years agosymbol: don't bother to set TeX name if user did not specified one.
Alexei Sheplyakov [Thu, 16 Oct 2008 11:43:32 +0000 (15:43 +0400)]
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).

11 years agosymbol: remove return_type_tinfo() and return_type() (shrink symbol by 8 bytes)
Alexei Sheplyakov [Fri, 17 Oct 2008 10:56:54 +0000 (14:56 +0400)]
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.

11 years agoWipe out remnants of custom RTTI.
Alexei Sheplyakov [Fri, 17 Oct 2008 09:41:01 +0000 (13:41 +0400)]
Wipe out remnants of custom RTTI.

Custom RTTI considered harmful, final part.

11 years agoregistered_class_info: use typeid() instead of tinfo_static.
Alexei Sheplyakov [Wed, 15 Oct 2008 11:32:11 +0000 (15:32 +0400)]
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.

11 years agoA better return_type_tinfo() mechanism.
Alexei Sheplyakov [Fri, 17 Oct 2008 09:15:03 +0000 (13:15 +0400)]
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().

11 years agocalchash(): use type_info::name() instead of tinfo().
Alexei Sheplyakov [Wed, 15 Oct 2008 11:32:11 +0000 (15:32 +0400)]
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.

11 years agoindexed::eval: use standard C++ RTTI.
Alexei Sheplyakov [Wed, 15 Oct 2008 11:32:11 +0000 (15:32 +0400)]
indexed::eval: use standard C++ RTTI.

Custom RTTI considered harmful, part 3.

11 years agobasic, expairseq: use standard C++ RTTI in compare(), is_equal(), match(), etc.
Alexei Sheplyakov [Wed, 15 Oct 2008 11:32:11 +0000 (15:32 +0400)]
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=(),
* expairseq.cpp: use standard C++ RTTI in match(), make_flat(),

11 years agois_exactly_a: use typeid() to check the type of expression.
Alexei Sheplyakov [Wed, 15 Oct 2008 11:32:11 +0000 (15:32 +0400)]
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.

11 years agoptr.h: use unsigned int to store reference counts (in order to save memory).
Alexei Sheplyakov [Wed, 15 Oct 2008 06:16:07 +0000 (10:16 +0400)]
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.

11 years agoRewritten heuristic and PRS GCD for univariate polynomials, added benchmark.
Alexei Sheplyakov [Sun, 19 Oct 2008 17:27:14 +0000 (21:27 +0400)]
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).

11 years agopolynomial: introduce a helper function to divide polynomial by ring element.
Alexei Sheplyakov [Tue, 14 Oct 2008 06:44:07 +0000 (10:44 +0400)]
polynomial: introduce a helper function to divide polynomial by ring element.

11 years agomod_gcd: naive hack to chose a 'good' prime (to speed up gcd computation).
Alexei Sheplyakov [Tue, 14 Oct 2008 06:37:42 +0000 (10:37 +0400)]
mod_gcd: naive hack to chose a 'good' prime (to speed up gcd computation).

11 years ago[bugfix] remainder_in_ring: using exact division is plain wrong.
Alexei Sheplyakov [Mon, 29 Sep 2008 05:58:35 +0000 (09:58 +0400)]
[bugfix] remainder_in_ring: using exact division is plain wrong.

11 years ago[bugfix] normalize_in_ring: don't set the leading coefficient to 1.
Alexei Sheplyakov [Mon, 29 Sep 2008 05:53:46 +0000 (09:53 +0400)]
[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.

11 years ago[trivial] excompiler.cpp: shut up some silly compiler warnings.
Alexei Sheplyakov [Thu, 25 Sep 2008 09:19:57 +0000 (13:19 +0400)]
[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.

11 years agoMerge branch 'master' of git://
Jens Vollinga [Tue, 30 Sep 2008 09:47:25 +0000 (11:47 +0200)]
Merge branch 'master' of git://

11 years agoReplaced class UniPoly by cl_UP_MI.
Jens Vollinga [Mon, 29 Sep 2008 15:38:46 +0000 (17:38 +0200)]
Replaced class UniPoly by cl_UP_MI.

11 years ago- Added options argument to factor(). Added flag factor_options::all that lets
Jens Vollinga [Fri, 26 Sep 2008 09:07:02 +0000 (11:07 +0200)]
- Added options argument to factor(). Added flag factor_options::all that lets
  factor() act on all polynomial subexpressions.
- Added more comments.

11 years agoImplemented modular GCD algorithm for univariate polynomials.
Alexei Sheplyakov [Sat, 20 Sep 2008 19:18:46 +0000 (23:18 +0400)]
Implemented modular GCD algorithm for univariate polynomials.

11 years agoWipe out the old (bison/flex generated) parser.
Alexei Sheplyakov [Sun, 14 Sep 2008 03:13:01 +0000 (07:13 +0400)]
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
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.

11 years agocheck: time_parser.cpp: don't run the same benchmark twice.
Alexei Sheplyakov [Sun, 14 Sep 2008 02:57:21 +0000 (06:57 +0400)]
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

11 years agoDocument the new parser, provide an example.
Alexei Sheplyakov [Sun, 14 Sep 2008 02:41:12 +0000 (06:41 +0400)]
Document the new parser, provide an example.

11 years agoUse the new parser in the ex(const string&, lst&) ctor.
Alexei Sheplyakov [Sun, 14 Sep 2008 02:24:29 +0000 (06:24 +0400)]
Use the new parser in the ex(const string&, lst&) ctor.

Note: this is certainly not the optimal way to use the parser. It's provided
for backward compatibility only.

11 years agoParser can parse (some) floating point numbers now.
Alexei Sheplyakov [Sun, 14 Sep 2008 02:01:53 +0000 (06:01 +0400)]
Parser can parse (some) floating point numbers now.

11 years agoparser: add necessary checks to operator() to stop accepting nonsense.
Alexei Sheplyakov [Sat, 13 Sep 2008 23:26:33 +0000 (03:26 +0400)]
parser: add necessary checks to operator() to stop accepting nonsense.

Since the parser is recursive parse_* methods (in particular,
parse_binop_rhs()) does NOT check if the last unparsed token is valid.
Thus parse_expression() stops if it encounters an unknown token. That's
why parser::operator() needs to make sure nothing is left in the input

11 years ago[bugfix] parser::parse_literal_expr(): don't forget to consume the token...
Alexei Sheplyakov [Sat, 13 Sep 2008 22:36:16 +0000 (02:36 +0400)]
[bugfix] parser::parse_literal_expr(): don't forget to consume the token...

... so parser won't process it twice (and get either spurious error or
wrong result).

11 years ago[bugfix]: parser::parse_unary_expr() parses '-a-b' correctly now.
Alexei Sheplyakov [Sat, 13 Sep 2008 23:19:05 +0000 (03:19 +0400)]
[bugfix]: parser::parse_unary_expr() parses '-a-b' correctly now.

Also added regression test.

11 years agoginac.h: include parser.hpp
Alexei Sheplyakov [Sat, 13 Sep 2008 01:12:31 +0000 (05:12 +0400)]
ginac.h: include parser.hpp

11 years agoparser: change order of the constructor optional arguments.
Alexei Sheplyakov [Sat, 13 Sep 2008 00:55:23 +0000 (04:55 +0400)]
parser: change order of the constructor optional arguments.

Functions/methods having multiple optional arguments are not very convenient
to use in C++ (to put it mildly). Shuffle parser ctor arguments so not so
frequently used argument is the last one.

11 years agoparser: allow read/write access to symbol table and strictness.
Alexei Sheplyakov [Sat, 13 Sep 2008 00:40:12 +0000 (04:40 +0400)]
parser: allow read/write access to symbol table and strictness.

Intended usage:

parser reader;
ifstream input_file1, input_file2;
// read the first file...
ex e1 = reader(input_file1);
// ... add extra entry into the symbol table used by parser
symbol x;
parser.get_syms()["x"] = x;
// Disable the parser to introduce new symbols, e.g. to ensure the expression
// in input_file2 contains the same symbols as e1 (read from input_file1).
parser.strict = true;
ex e2;
try {
e2 = reader(input_file2);
} catch (...) {

11 years agoparser: map input strings onto arbitrary expressions (not only symbols).
Alexei Sheplyakov [Sat, 13 Sep 2008 00:30:22 +0000 (04:30 +0400)]
parser: map input strings onto arbitrary expressions (not only symbols).

So it's possible to make abbreviations, e.g.

symbol x;
symtab table;
table["x"] = x + log(x) + 1;
parser reader(table);
ex e = reader("1 + x^2 + 5*x^3");

11 years ago[BUGFIX] parser.hpp: fix include guard so the header is actually usable.
Alexei Sheplyakov [Sat, 13 Sep 2008 00:21:27 +0000 (04:21 +0400)]
[BUGFIX] parser.hpp: fix include guard so the header is actually usable.

11 years ago[nitpick] power::expand_add(): don't use int instead of std::size_t.
Alexei Sheplyakov [Fri, 12 Sep 2008 15:55:36 +0000 (19:55 +0400)]
[nitpick] power::expand_add(): don't use int instead of std::size_t.

This shuts a few 'comparison between signed and unsigned integer expressions'

11 years ago[nitpick] inifcns_nstdsums: don't use int instead of std::size_t.
Alexei Sheplyakov [Fri, 12 Sep 2008 15:55:36 +0000 (19:55 +0400)]
[nitpick] inifcns_nstdsums: don't use int instead of std::size_t.

This shuts up quite a number of 'comparison between signed and unsigned
integer expressions'  warnings.

11 years ago[nitpick] don't use int instead of std::size_t.
Alexei Sheplyakov [Fri, 12 Sep 2008 15:55:36 +0000 (19:55 +0400)]
[nitpick] don't use int instead of std::size_t.

This shuts up (some of) 'comparison between signed and unsigned integer
expressions'  warnings.

11 years agoG_numeric: use cl_N and int to manipulate numbers (instead of ex).
Alexei Sheplyakov [Thu, 11 Sep 2008 11:16:21 +0000 (15:16 +0400)]
G_numeric: use cl_N and int to manipulate numbers (instead of ex).

Convert helper functions G_do_hoelder and G_do_trafo in the same manner,
update all call sites. This should speed up numerical calculation of
multiple polylogarithms a little bit, and reduce the memory usage.

11 years agoG_numeric: put convergence/acceleration transofrmations into helper functions.
Alexei Sheplyakov [Wed, 10 Sep 2008 11:43:35 +0000 (15:43 +0400)]
G_numeric: put convergence/acceleration transofrmations into helper functions.

This is simple code move, everything else should be considered a bug.
The helper functions (as well as G_numeric itself) will be improved by
subsequent patches.

11 years agomatch() (find()): use exmap (exset) to store matched subexpressions.
Alexei Sheplyakov [Fri, 12 Sep 2008 10:55:42 +0000 (14:55 +0400)]
match() (find()): use exmap (exset) to store matched subexpressions.

There's no need to re-invent associative arrays and wrap them into
a GiNaC class.

11 years agoexpairseq::match(): remove the code which works around basic::match bug.
Alexei Sheplyakov [Thu, 11 Sep 2008 12:59:30 +0000 (16:59 +0400)]
expairseq::match(): remove the code which works around basic::match bug.

basic::match() used to have side effects in a case of a failed match. As
a result of that bug exparsed::match did not work correctly in some cases,
see [1] for more details. These false negatives were worked around by [2].
Now that match() has no unwanted side effects [3] we don't need any work
arounds any more.

Just in a case add a regression test (from [1]).

[2] Commit 73f0ce4cf8d91f073f35a45443f5fbe886921c5c ("Fixed bugs in ::match").
[3] Commit 192ed7390b7b2b705ad100e3db0a92eedd2b20ad ("match: don't modify
    subexpression list if expression doesn't match the pattern.").

11 years agoFixed various bugs in multivariate factorization.
Jens Vollinga [Thu, 18 Sep 2008 18:26:37 +0000 (20:26 +0200)]
Fixed various bugs in multivariate factorization.

11 years agoMerge branch 'master' of git://
Jens Vollinga [Tue, 9 Sep 2008 20:42:50 +0000 (22:42 +0200)]
Merge branch 'master' of git://

11 years agoBug fix related to the usage of int instead of cl_I.
Jens Vollinga [Tue, 9 Sep 2008 20:41:39 +0000 (22:41 +0200)]
Bug fix related to the usage of int instead of cl_I.

11 years agoUpdated NEWS.
Jens Vollinga [Tue, 9 Sep 2008 20:41:24 +0000 (22:41 +0200)]
Updated NEWS.

11 years agobuild: shut up automake warnings, don't use GNU make extensions.
Alexei Sheplyakov [Tue, 9 Sep 2008 10:44:25 +0000 (14:44 +0400)]
build: shut up automake warnings, don't use GNU make extensions.

Not that I really care about non-GNU makes, but those warnings are a bit
annoying and can hide useful ones.

11 years agobuild: put (almost) all auto* tools scripts into the config directory.
Alexei Sheplyakov [Mon, 8 Sep 2008 07:53:30 +0000 (11:53 +0400)]
build: put (almost) all auto* tools scripts into the config directory.

So I can just rm -rf it to clean up the repository.

11 years agoAllow user to disable GiNaC::compile_ex (e.g. for security reasons).
Alexei Sheplyakov [Mon, 8 Sep 2008 07:09:20 +0000 (11:09 +0400)]
Allow user to disable GiNaC::compile_ex (e.g. for security reasons).

configure takes --{disable,enable}-excompiler argument now. It can be
used to disable GiNaC::compile_ex (default is to enable it).

GINAC_EXCOMPILER: new macro. Checks for libdl, allows user to disable
GiNaC::compile_ex. Also it doesn't bother to check for libdl on MinGW. use GINAC_EXCOMPILER to check for libdl.

11 years agoconfigure: run important checks first (and bail out if something is missing).
Alexei Sheplyakov [Sun, 7 Sep 2008 18:53:07 +0000 (22:53 +0400)]
configure: run important checks first (and bail out if something is missing).

Don't bother to check for optional stuff if CLN and/or standard C++ headers
are missing.

11 years agoconfigure: don't bother to run checks which can be done at the compile time.
Alexei Sheplyakov [Sun, 7 Sep 2008 18:47:01 +0000 (22:47 +0400)]
configure: don't bother to run checks which can be done at the compile time.

Don't check for sizeof of various types, this can be done at the compile time.
GCC optimizes away these checks, so the actual code is the same.

11 years agoutils.h: use <stdint.h> (if available) instead of reinventing it.
Alexei Sheplyakov [Sun, 7 Sep 2008 18:17:55 +0000 (22:17 +0400)]
utils.h: use <stdint.h> (if available) instead of reinventing it.

The argument of golden_ratio_hash() is as an integer of the same size as
a void* pointer. Unfortunately ISO C++ 98 does not provide suitable typedef.

* use <stdint.h> if available and define p_int to uintptr_t. Note: AC_PROG_CC
  already checks for this header, so no extra checks are necessary.
* as a fallback define p_int to be unsigned long, this works on most systems
  I know of (the only exception is woe64).

While at it, stop including "config.h" unconditionally.

11 years agoconfigure: don't check for sizeof(long double), we don't use it.
Alexei Sheplyakov [Sat, 6 Sep 2008 05:21:18 +0000 (09:21 +0400)]
configure: don't check for sizeof(long double), we don't use it.

11 years agobuild: faster check for standard C++ headers.
Alexei Sheplyakov [Sat, 6 Sep 2008 04:51:19 +0000 (08:51 +0400)]
build: faster check for standard C++ headers.

Include them all into a test program and check if it compiles (in order to reduce
the run time of the `configure' script).

11 years agobuild: don't run any ${host} binaries while checking for readline.
Alexei Sheplyakov [Mon, 9 Jun 2008 12:21:30 +0000 (16:21 +0400)]
build: don't run any ${host} binaries while checking for readline.

Now GiNaC (to be more precise, ginsh) can be easily cross compiled.
However, ancient versions of readline (<= 4.2) are not supported any more.

11 years agodon't mention CVS any more, describe how to install from git.
Alexei Sheplyakov [Mon, 8 Sep 2008 07:50:12 +0000 (11:50 +0400)]
don't mention CVS any more, describe how to install from git.

11 years agomatch: don't modify subexpression list if expression doesn't match the pattern.
Alexei Sheplyakov [Tue, 15 Jul 2008 17:08:22 +0000 (21:08 +0400)]
match: don't modify subexpression list if expression doesn't match the pattern.

As of now the match() method modifies the list of matched subexpressions
(its second argument) even if the expression in question does not match
the pattern. Thus, this simple program

 #include <ginac/ginac.h>
 #include <iostream>
using namespace GiNaC;

int main(int argc, char** argv)
symbol x;
ex e = pow(x, 5);
ex pattern = pow(wild(), -1);
lst repl;
bool test = e.match(pattern, repl);
std::cout << "repl = " << repl << std::endl;


repl = {x}

Such behaviour is a bit unexpected. Sometimes it confuses even GiNaC
developers, see e.g.

Hence this patch. Now the above program prints

repl = {}

as expected.

11 years ago[BUGFIX] Reclaiming the memory allocated for static objects *is* necessary.
Alexei Sheplyakov [Tue, 19 Aug 2008 11:39:46 +0000 (15:39 +0400)]
[BUGFIX] Reclaiming the memory allocated for static objects *is* necessary.

GiNaC allocates memory for static objects (i.e. flyweights, remember tables,
etc), but doesn't free it. This is OK if the program lifetime matches libginac
lifetime, since the OS will reclaim that memory anyway.
However, if the program lifetime is different from that of libginac, this
turns into a memory leak. This happens if someone dlopen's, and
dlclose's it later on (read: if someone uses GiNaC via scripting language

symbol::autoname_prefix(): there's no need for dynamical memory allocation.
remember_table::remember_tables(): likewise.
function::registered_functions(): likewise.
lib_init::~lib_init(): if library usage count drops to 0, reclaim the memory
                       allocated for flyweights.

11 years agosymbol: get rid of assign/unassign (for performance and other reasons).
Alexei Sheplyakov [Tue, 9 Sep 2008 07:14:57 +0000 (11:14 +0400)]
symbol: get rid of assign/unassign (for performance and other reasons).

* symbol::eval() is trivial now, so compiler can inline it in some cases.
* symbol takes less memory.
* no functionality is lost (as C++ has associative arrays).

11 years agoginsh: use exmap for storing assigned symbols.
Alexei Sheplyakov [Tue, 9 Sep 2008 06:39:26 +0000 (10:39 +0400)]
ginsh: use exmap for storing assigned symbols.

C++ already have associative arrays, there's no need to re-invent them.

11 years agomultiple zeta values: make crandall_Y_loop helper function reentrant.
Alexei Sheplyakov [Fri, 29 Aug 2008 19:44:51 +0000 (23:44 +0400)]
multiple zeta values: make crandall_Y_loop helper function reentrant.

* Move crB and crG variables into initcX function (the only user of these
* Pass crX coefficients to crandall_Y_loop instead of using a global variable.
* While at it make crandall_Y_loop and initcX functions static.

11 years agomultiple zeta values: make crandall_Z helper function reentrant.
Alexei Sheplyakov [Fri, 29 Aug 2008 19:44:51 +0000 (23:44 +0400)]
multiple zeta values: make crandall_Z helper function reentrant.

Pass the f_kj coefficients as an arguments to crandall_Z and calc_f
functions instead of using global variables.

11 years agoparser: improve error reporting a little bit.
Alexei Sheplyakov [Mon, 25 Aug 2008 15:08:36 +0000 (19:08 +0400)]
parser: improve error reporting a little bit.

Introduce class 'parse_error' (which contain some info about location of
the error) and throw it on parse errors.

N.B.: the actual info is a bit inaccurate because lexer doesn't track
the location properly yet.

11 years agolexer: when switching to another output stream, clean last read character.
Alexei Sheplyakov [Mon, 25 Aug 2008 13:49:58 +0000 (17:49 +0400)]
lexer: when switching to another output stream, clean last read character.

Otherwise we prepend to the current stream the last character read from
the previous stream, which is obviously incorrect.

11 years agoFixed bug in unvariate factorization. Bound for lifting was using a ordinary
Jens Vollinga [Mon, 8 Sep 2008 17:17:56 +0000 (19:17 +0200)]
Fixed bug in unvariate factorization. Bound for lifting was using a ordinary
int instead of a cl_I.

11 years agoAdded missing code for multivariate factorization.
Jens Vollinga [Mon, 8 Sep 2008 16:32:27 +0000 (18:32 +0200)]
Added missing code for multivariate factorization.

11 years agoFixed bug. G() ignored the imaginary parts of the arguments.
Jens Vollinga [Mon, 8 Sep 2008 16:17:51 +0000 (18:17 +0200)]
Fixed bug. G() ignored the imaginary parts of the arguments.

11 years agoAdded internal code for multivariate factorization.
Jens Vollinga [Wed, 27 Aug 2008 15:25:16 +0000 (17:25 +0200)]
Added internal code for multivariate factorization.

11 years agogcd_pf_pow_pow: deobfuscate a little bit (no functional changes).
Alexei Sheplyakov [Mon, 25 Aug 2008 12:57:38 +0000 (16:57 +0400)]
gcd_pf_pow_pow: deobfuscate a little bit (no functional changes).


if (foo)
return bar();
return baz();

instead of

if (foo) {
return bar();
} else {
return baz();

This makes the code a little bit more readable.

11 years agogcd_pf_pow: get rid of duplicate code.
Alexei Sheplyakov [Mon, 25 Aug 2008 12:57:02 +0000 (16:57 +0400)]
gcd_pf_pow: get rid of duplicate code.

This function (which helps gcd() handle partially factored expressions)
contained two copies of the same code. Remove one redundant copy.

11 years agointroduce gcd_pf_pow_pow: gcd helper to handle partially factored expressions.
Alexei Sheplyakov [Mon, 25 Aug 2008 12:56:04 +0000 (16:56 +0400)]
introduce gcd_pf_pow_pow: gcd helper to handle partially factored expressions.

gcd_pf_pow_pow handles the case when both arguments of gcd() are powers.

N.B. the actual code moved from gcd_pf_pow, no functional changes.

11 years agogcd_pf_{pow, mul}: don't check if the arguments are polynomials.
Alexei Sheplyakov [Mon, 25 Aug 2008 12:55:42 +0000 (16:55 +0400)]
gcd_pf_{pow, mul}: don't check if the arguments are polynomials.

These functions gets called only from gcd(), which does this check
on its own.

11 years agogcd_pf_mul: get rid of duplicate code.
Alexei Sheplyakov [Mon, 25 Aug 2008 12:55:13 +0000 (16:55 +0400)]
gcd_pf_mul: get rid of duplicate code.

This function (which helps gcd() handle partially factored expressions)
contained two copies of the same code. Remove one redundant copy.

11 years agogcd(): allow user to override (some of) heuristics.
Alexei Sheplyakov [Mon, 25 Aug 2008 12:54:46 +0000 (16:54 +0400)]
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 5:

* gcd(): don't use heuristic GCD algorithm if gcd_options::no_heur_gcd
  flag is set.
* gcd(): don't handle partially factored expressions in a special way
  if gcd_options::no_part_factored flag is set.

11 years agorefactor gcd() a little bit (no functional changes).
Alexei Sheplyakov [Mon, 25 Aug 2008 12:54:10 +0000 (16:54 +0400)]
refactor gcd() a little bit (no functional changes).

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 4:

refactor gcd() a little bit, so subsequent patch(es) won't be so big and ugly.

11 years agointroduce gcd_pf_mul: gcd helper to handle partially factored expressions.
Alexei Sheplyakov [Mon, 25 Aug 2008 12:53:47 +0000 (16:53 +0400)]
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.

11 years agointroduce gcd_pf_pow: gcd helper to handle partially factored expressions.
Alexei Sheplyakov [Mon, 25 Aug 2008 12:53:07 +0000 (16:53 +0400)]
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.

11 years agogcd: allow user to override (some of) heuristics.
Alexei Sheplyakov [Mon, 25 Aug 2008 12:52:45 +0000 (16:52 +0400)]
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.

11 years agoinifscn_nstdsums: make functions handling Li/G transformations reentrant.
Alexei Sheplyakov [Sun, 24 Aug 2008 11:25:24 +0000 (15:25 +0400)]
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

11 years agoBail out if both autogen and autogen'erated file(s) are missing.
Alexei Sheplyakov [Thu, 21 Aug 2008 22:42:17 +0000 (02:42 +0400)]
Bail out if both autogen and autogen'erated file(s) are missing.

This makes the error message(s) more helpful.

11 years agoFaster, better (recursive descent) expression parser.
Alexei Sheplyakov [Tue, 19 Aug 2008 19:48:03 +0000 (23:48 +0400)]
Faster, better (recursive descent) expression parser.

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

From: Alexei Sheplyakov <>
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
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.


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 :-)


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)

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)


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 '-'


benchmark_and_plot $N_ini $N_fin $out_base