May 2010 - GiNaC-devel

[SCM] GiNaC -- a C++ library for symbolic computations branch, ginac_1-5, updated. release_1-4-0-239-g5fb8367
by git＠ginac.de 22 May '10

22 May '10

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GiNaC -- a C++ library for symbolic computations". The branch, ginac_1-5 has been updated via 5fb83676210401cc08fae91831514bac44502209 (commit) via 9c2ce1cc26735e268aae8142d9e5dbc5a9ba8ca3 (commit) from edf1ae46a926d0a718063c149b78c1b9a7ec2043 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 5fb83676210401cc08fae91831514bac44502209 Author: Richard Kreckel <kreckel(a)ginac.de> Date: Sat May 22 22:34:42 2010 +0200 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. commit 9c2ce1cc26735e268aae8142d9e5dbc5a9ba8ca3 Author: Richard Kreckel <kreckel(a)ginac.de> Date: Wed May 19 00:18:35 2010 +0200 Fix dangerous iterator use. This was detected by cppcheck and reported by Martin Ettl <ettl.martin(a)gmx.de>. ----------------------------------------------------------------------- Summary of changes: doc/tutorial/ginac.texi | 13 +++-- ginac/excompiler.cpp | 2 +- ginac/function.pl | 2 +- ginac/inifcns.cpp | 19 ++++++- ginac/inifcns_gamma.cpp | 26 +++++++++- ginac/inifcns_trans.cpp | 131 +++++++++++++++++++++++++++++++++++++++++++++- ginac/power.cpp | 21 ++++++-- 7 files changed, 195 insertions(+), 19 deletions(-) hooks/post-receive -- GiNaC -- a C++ library for symbolic computations

1 0

[SCM] GiNaC -- a C++ library for symbolic computations branch, master, updated. release_1-4-0-220-gff8b400
by git＠ginac.de 22 May '10

22 May '10

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GiNaC -- a C++ library for symbolic computations". The branch, master has been updated via ff8b400eb500618644231ed9e6f199c3b0b25135 (commit) via 1a5127603d93125b75ee51c94200faf0b586ef32 (commit) from e75c7a32a0ea156635aeec535b9cdf7d4bf3f9b9 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit ff8b400eb500618644231ed9e6f199c3b0b25135 Author: Richard Kreckel <kreckel(a)ginac.de> Date: Sat May 22 22:34:42 2010 +0200 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. commit 1a5127603d93125b75ee51c94200faf0b586ef32 Author: Richard Kreckel <kreckel(a)ginac.de> Date: Wed May 19 00:18:35 2010 +0200 Fix dangerous iterator use. This was detected by cppcheck and reported by Martin Ettl <ettl.martin(a)gmx.de>. ----------------------------------------------------------------------- Summary of changes: doc/tutorial/ginac.texi | 13 +++-- ginac/excompiler.cpp | 2 +- ginac/function.pl | 2 +- ginac/inifcns.cpp | 19 ++++++- ginac/inifcns_gamma.cpp | 26 +++++++++- ginac/inifcns_trans.cpp | 131 +++++++++++++++++++++++++++++++++++++++++++++- ginac/power.cpp | 21 ++++++-- 7 files changed, 195 insertions(+), 19 deletions(-) hooks/post-receive -- GiNaC -- a C++ library for symbolic computations

1 0

[SCM] GiNaC -- a C++ library for symbolic computations branch, master, updated. release_1-4-0-218-ge75c7a3
by git＠ginac.de 18 May '10

18 May '10

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GiNaC -- a C++ library for symbolic computations". The branch, master has been updated via e75c7a32a0ea156635aeec535b9cdf7d4bf3f9b9 (commit) via b2ea74ecbae56d737aacf2cbb418d7c9998718a4 (commit) via 5432feb4dae4c48f3b652d661aa323f07d20c00b (commit) via 8fcaff0d29e20d570c2936a27ce110326b76390e (commit) via 0c1db90c39613c27a088b760d68e8d59d4a12ee3 (commit) from b604136850dac1fa8016623349061f2a3b0085be (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit e75c7a32a0ea156635aeec535b9cdf7d4bf3f9b9 Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue May 18 00:23:03 2010 +0200 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. commit b2ea74ecbae56d737aacf2cbb418d7c9998718a4 Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue May 18 00:21:53 2010 +0200 Added `degree_vector' utility function. It's a generalization of degree(expr, var) for multivariate polynomials. commit 5432feb4dae4c48f3b652d661aa323f07d20c00b Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue May 18 00:20:08 2010 +0200 primpart_content: correctly handle monomials. Impact: fixes (rare) incorrect gcd calculation and (potential) segfault. Thanks to Aless Lasaruk for a bug report. commit 8fcaff0d29e20d570c2936a27ce110326b76390e Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue May 18 00:17:26 2010 +0200 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. commit 0c1db90c39613c27a088b760d68e8d59d4a12ee3 Author: Richard Kreckel <kreckel(a)ginac.de> Date: Mon May 17 08:37:08 2010 +0200 Fix URL of CODA. ----------------------------------------------------------------------- Summary of changes: check/Makefile.am | 4 +++ check/pgcd_infinite_loop.cpp | 41 +++++++++++++++++++++++++++++++++ doc/tutorial/ginac.texi | 2 +- ginac/polynomial/collect_vargs.cpp | 22 ++++++++++++++++- ginac/polynomial/collect_vargs.h | 31 +++++++++++++++++++++++++ ginac/polynomial/mgcd.cpp | 12 ++++++--- ginac/polynomial/pgcd.cpp | 12 +++++----- ginac/polynomial/primpart_content.cpp | 2 +- 8 files changed, 112 insertions(+), 14 deletions(-) create mode 100644 check/pgcd_infinite_loop.cpp hooks/post-receive -- GiNaC -- a C++ library for symbolic computations

1 0

[SCM] GiNaC -- a C++ library for symbolic computations branch, ginac_1-5, updated. release_1-4-0-237-gedf1ae4
by git＠ginac.de 18 May '10

18 May '10

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GiNaC -- a C++ library for symbolic computations". The branch, ginac_1-5 has been updated via edf1ae46a926d0a718063c149b78c1b9a7ec2043 (commit) via 6201dc3c6562e0b8c174129af382fd5745de048f (commit) via c13d5e0ed2ce6223bc6c4340bb00daf2e24ea923 (commit) via f28f24cf1228f0fa9cb0889d87a3f4039587ff92 (commit) via a7c70c1f9e0b906a8b95bffb04bc1266eb59f39d (commit) from 05f749ac2abb672f8e0a1cef938ea1e83e1255dc (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit edf1ae46a926d0a718063c149b78c1b9a7ec2043 Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue May 18 00:23:03 2010 +0200 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. commit 6201dc3c6562e0b8c174129af382fd5745de048f Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue May 18 00:21:53 2010 +0200 Added `degree_vector' utility function. It's a generalization of degree(expr, var) for multivariate polynomials. commit c13d5e0ed2ce6223bc6c4340bb00daf2e24ea923 Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue May 18 00:20:08 2010 +0200 primpart_content: correctly handle monomials. Impact: fixes (rare) incorrect gcd calculation and (potential) segfault. Thanks to Aless Lasaruk for a bug report. commit f28f24cf1228f0fa9cb0889d87a3f4039587ff92 Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue May 18 00:17:26 2010 +0200 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. commit a7c70c1f9e0b906a8b95bffb04bc1266eb59f39d Author: Richard Kreckel <kreckel(a)ginac.de> Date: Mon May 17 08:37:08 2010 +0200 Fix URL of CODA. ----------------------------------------------------------------------- Summary of changes: check/Makefile.am | 4 +++ check/pgcd_infinite_loop.cpp | 41 +++++++++++++++++++++++++++++++++ doc/tutorial/ginac.texi | 2 +- ginac/polynomial/collect_vargs.cpp | 22 ++++++++++++++++- ginac/polynomial/collect_vargs.h | 31 +++++++++++++++++++++++++ ginac/polynomial/mgcd.cpp | 12 ++++++--- ginac/polynomial/pgcd.cpp | 12 +++++----- ginac/polynomial/primpart_content.cpp | 2 +- 8 files changed, 112 insertions(+), 14 deletions(-) create mode 100644 check/pgcd_infinite_loop.cpp hooks/post-receive -- GiNaC -- a C++ library for symbolic computations

1 0

Factorization Bug
by Aless Lasaruk 17 May '10

17 May '10

Dear GiNaC developers, i would like to report a bug in polynomial factorization. I want to factorize the following multivariate polynomial (P. S. Wang, Test case 9 in the attached publication): 792*z^8*w^4*x^3*y^4*u^7+24*z^4*w^4*x^2*y^3*u^4+264*z^8*w^3*x^2*y^7*u^5+198*z^4*w^5*x^5*y*u^6+110*z^2*w^3*x^5*y^4*u^6-120*z^8*w*x^4*u^6-480*z^5*w*x^4*y^6*u^8-720*z^7*x^3*y^3*u^7+165*z^4*w^2*x^4*y*u^5+450*z^8*w^6*x^2*y*u^8+40*z^2*w^3*x^3*y^3*u^6-288*z^7*w^2*x^3*y^6*u^6+250*z^6*w^4*x^2*y^4*u^8+576*z^7*w^7*x^2*y^4*u^8-80*z^6*w^2*x^5*y^3*u^7-144*z^8*w^4*x^5*u^7+120*z^4*w*x^2*y^6*u^6+320*z^5*w^5*x^2*y^7*u^8+192*z^7*w^6*x*y^7*u^6-12*z^4*w^3*x^3*y^5*u^6-36*z^4*w^4*x^4*y^2*u^8+72*z^4*w^5*x^3*u^6-20*z^2*w^2*x^4*y^5*u^8+660*z^8*w*x^2*y^4*u^6+66*z^4*w^4*x^4*y^4*u^4+440*z^6*w^2*x^3*y^7*u^7-30*z^4*w*x^3*y^2*u^7-48*z^8*w^3*x^4*y^3*u^5+72*z^6*w^2*x*y^6*u^4-864*z^7*w^3*x^4*y^3*u^8+480*z^7*w^4*x*y^4*u^7+60*z^4*w^2*x^2*u^5+375*z^8*w^3*x*y*u^7+150*z^8*w^5*x*y^4*u^6+180*z^6*x*y^3*u^5+216*z^6*w^3*x^2*y^3*u^6 GiNaC crashes with the following exception: malloc: *** mmap(size=3774734336) failed (error code=12) *** error: can't allocate region *** set a breakpoint in malloc_error_break to debug terminate called after throwing an instance of 'std::bad_alloc' what(): St9bad_alloc MfG, Aless -- Aless Lasaruk Scientific Assistant, FORWISS Room 204, ITZ, Innstrasse 43 Universität Passau D-94030 Passau (Germany) Mail: lasaruk(a)uni-passau.de Tel.: +49(0)851/509-3173 Fax : +49(0)851/509-3142

2 2

[PATCH 4/4] [BUGFIX] pgcd(), chinrem_gcd(): use appropriate definition of the degree.
by Alexei Sheplyakov 17 May '10

17 May '10

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. --- check/pgcd_infinite_loop.cpp | 8 ++++++-- ginac/polynomial/mgcd.cpp | 12 ++++++++---- ginac/polynomial/pgcd.cpp | 10 ++++++---- 3 files changed, 20 insertions(+), 10 deletions(-) diff --git a/check/pgcd_infinite_loop.cpp b/check/pgcd_infinite_loop.cpp index 013b746..ae39f1d 100644 --- a/check/pgcd_infinite_loop.cpp +++ b/check/pgcd_infinite_loop.cpp @@ -26,12 +26,16 @@ static const string srep("\ int main(int argc, char** argv) { - cout << "Checking for more pgcd() bugs (infinite loop) ... " << flush; + cout << "Checking for more pgcd() bugs (infinite loop, miscalculation) ... " << flush; parser the_parser; ex e = the_parser(srep); const symbol x = ex_to<symbol>(the_parser.get_syms()["x"]); ex g = gcd(e, e.diff(x)); + ex should_be = the_parser(string("u^4*z^2")); + if (!(g-should_be).expand().is_zero()) { + cout << "GCD was miscomputed. " << flush; + return 1; + } cout << "not found. " << flush; - cout << g << endl << flush; return 0; } diff --git a/ginac/polynomial/mgcd.cpp b/ginac/polynomial/mgcd.cpp index bf30b5c..24da934 100644 --- a/ginac/polynomial/mgcd.cpp +++ b/ginac/polynomial/mgcd.cpp @@ -27,6 +27,7 @@ #include "primes_factory.h" #include "divide_in_z_p.h" #include "poly_cra.h" +#include <numeric> // std::accumulate #include <cln/integer.h> @@ -58,12 +59,15 @@ ex chinrem_gcd(const ex& A_, const ex& B_, const exvector& vars) const cln::cl_I g_lc = cln::gcd(a_lc, b_lc); const ex& x(vars.back()); - int n = std::min(A.degree(x), B.degree(x)); + exp_vector_t n = std::min(degree_vector(A, vars), degree_vector(B, vars)); + const int nTot = std::accumulate(n.begin(), n.end(), 0); const cln::cl_I A_max_coeff = to_cl_I(A.max_coefficient()); const cln::cl_I B_max_coeff = to_cl_I(B.max_coefficient()); - const cln::cl_I lcoeff_limit = (cln::cl_I(1) << n)*cln::abs(g_lc)* + + const cln::cl_I lcoeff_limit = (cln::cl_I(1) << nTot)*cln::abs(g_lc)* std::min(A_max_coeff, B_max_coeff); + cln::cl_I q = 0; ex H = 0; @@ -83,8 +87,8 @@ ex chinrem_gcd(const ex& A_, const ex& B_, const exvector& vars) const cln::cl_I Cp_lc = integer_lcoeff(Cp, vars); const cln::cl_I nlc = smod(recip(Cp_lc, p)*g_lcp, p); Cp = (Cp*numeric(nlc)).expand().smod(pnum); - int cp_deg = Cp.degree(x); - if (cp_deg == 0) + exp_vector_t cp_deg = degree_vector(Cp, vars); + if (zerop(cp_deg)) return numeric(g_lc); if (zerop(q)) { H = Cp; diff --git a/ginac/polynomial/pgcd.cpp b/ginac/polynomial/pgcd.cpp index fac3735..a33b02d 100644 --- a/ginac/polynomial/pgcd.cpp +++ b/ginac/polynomial/pgcd.cpp @@ -80,7 +80,8 @@ ex pgcd(const ex& A, const ex& B, const exvector& vars, const long p) const ex lc_gcd = euclid_gcd(AL, BL, mainvar, p); // The estimate of degree of the gcd of Ab and Bb - int gcd_deg = std::min(degree(Aprim, mainvar), degree(Bprim, mainvar)); + exp_vector_t gcd_deg = std::min(degree_vector(Aprim, restvars), + degree_vector(Bprim, restvars)); eval_point_finder::value_type b; eval_point_finder find_eval_point(p); @@ -105,8 +106,11 @@ ex pgcd(const ex& A, const ex& B, const exvector& vars, const long p) const cln::cl_I correct_lc = smod(lcb_gcd*recip(Cblc, p), p); Cb = (Cb*numeric(correct_lc)).smod(pn); + const exp_vector_t img_gcd_deg = degree_vector(Cb, restvars); + // Test for relatively prime polynomials + if (zerop(img_gcd_deg)) + return cont_gcd; // Test for unlucky homomorphisms - const int img_gcd_deg = Cb.degree(restvars.back()); if (img_gcd_deg < gcd_deg) { // The degree decreased, previous homomorphisms were // bad, so we have to start it all over. @@ -121,8 +125,6 @@ ex pgcd(const ex& A, const ex& B, const exvector& vars, const long p) // evaluation point is bad. Skip it. continue; } - if (img_gcd_deg == 0) - return cont_gcd; // Image has the same degree as the previous one // (or at least not higher than the limit) -- 1.7.1

1 0

[PATCH 3/4] Added `degree_vector' utility function.
by Alexei Sheplyakov 17 May '10

17 May '10

It's a generalization of degree(expr, var) for multivariate polynomials. --- ginac/polynomial/collect_vargs.cpp | 12 ++++++++++++ ginac/polynomial/collect_vargs.h | 31 +++++++++++++++++++++++++++++++ 2 files changed, 43 insertions(+), 0 deletions(-) diff --git a/ginac/polynomial/collect_vargs.cpp b/ginac/polynomial/collect_vargs.cpp index 2593268..c4368fb 100644 --- a/ginac/polynomial/collect_vargs.cpp +++ b/ginac/polynomial/collect_vargs.cpp @@ -177,6 +177,18 @@ ex lcoeff_wrt(ex e, const exvector& x) return ec.rbegin()->second; } +exp_vector_t degree_vector(ex e, const exvector& vars) +{ + e = e.expand(); + exp_vector_t dvec(vars.size()); + for (std::size_t i = vars.size(); i-- != 0; ) { + const int deg_i = e.degree(vars[i]); + e = e.coeff(vars[i], deg_i); + dvec[i] = deg_i; + } + return dvec; +} + cln::cl_I integer_lcoeff(const ex& e, const exvector& vars) { ex_collect_t ec; diff --git a/ginac/polynomial/collect_vargs.h b/ginac/polynomial/collect_vargs.h index 44c3d72..a927c3f 100644 --- a/ginac/polynomial/collect_vargs.h +++ b/ginac/polynomial/collect_vargs.h @@ -28,10 +28,34 @@ #include <cln/integer.h> #include <utility> // for std::pair #include <vector> +#include <algorithm> // std::lexicographical_compare namespace GiNaC { typedef std::vector<int> exp_vector_t; + +static inline bool operator<(const exp_vector_t& v1, const exp_vector_t& v2) +{ + return std::lexicographical_compare(v1.rbegin(), v1.rend(), + v2.rbegin(), v2.rend()); +} + +static inline bool operator>(const exp_vector_t& v1, const exp_vector_t& v2) +{ + if (v1 == v2) + return false; + return !(v1 < v2); +} + +static inline bool zerop(const exp_vector_t& v) +{ + for (exp_vector_t::const_reverse_iterator i = v.rbegin(); i != v.rend(); ++i) { + if (*i != 0) + return false; + } + return true; +} + typedef std::vector<std::pair<exp_vector_t, ex> > ex_collect_t; extern void @@ -46,6 +70,13 @@ ex_collect_to_ex(const ex_collect_t& ec, const exvector& x); */ extern ex lcoeff_wrt(ex e, const exvector& x); + +/** + * Degree vector of a leading term of a multivariate polynomial. + * (generalization of degree(expr, var)) + */ +extern exp_vector_t degree_vector(ex e, const exvector& vars); + /** * Leading coefficient c \in R (where R = Z or Z_p) of a multivariate * polynomial e \in R[x_0, \ldots, x_n] -- 1.7.1

1 0

[PATCH 2/4] [BUGFIX] primpart_content: correctly handle monomials.
by Alexei Sheplyakov 17 May '10

17 May '10

Impact: fixes (rare) incorrect gcd calculation and (potential) segfault. Thanks to Aless Lasaruk for a bug report. --- ginac/polynomial/collect_vargs.cpp | 10 ++++++++-- ginac/polynomial/primpart_content.cpp | 2 +- 2 files changed, 9 insertions(+), 3 deletions(-) diff --git a/ginac/polynomial/collect_vargs.cpp b/ginac/polynomial/collect_vargs.cpp index 89c3b8b..2593268 100644 --- a/ginac/polynomial/collect_vargs.cpp +++ b/ginac/polynomial/collect_vargs.cpp @@ -148,8 +148,14 @@ ex_collect_to_ex(const ex_collect_t& ec, const GiNaC::exvector& vars) exvector tv; tv.reserve(vars.size() + 1); for (std::size_t j = 0; j < vars.size(); ++j) { - if (ec[i].first[j] != 0) - tv.push_back(power(vars[j], ec[i].first[j])); + const exp_vector_t& exp_vector(ec[i].first); + + bug_on(exp_vector.size() != vars.size(), + "expected " << vars.size() << " variables, " + "expression has " << exp_vector.size() << " instead"); + + if (exp_vector[j] != 0) + tv.push_back(power(vars[j], exp_vector[j])); } tv.push_back(ec[i].second); ex tmp = (new mul(tv))->setflag(status_flags::dynallocated); diff --git a/ginac/polynomial/primpart_content.cpp b/ginac/polynomial/primpart_content.cpp index f703ee7..694f29d 100644 --- a/ginac/polynomial/primpart_content.cpp +++ b/ginac/polynomial/primpart_content.cpp @@ -62,7 +62,7 @@ void primpart_content(ex& pp, ex& c, ex e, const exvector& vars, // p_1(x_n) p_2(x_0, \ldots, x_{n-1}) c = ec.rbegin()->second; ec.rbegin()->second = ex1; - pp = ex_collect_to_ex(ec, vars).expand().smod(numeric(p)); + pp = ex_collect_to_ex(ec, rest_vars).expand().smod(numeric(p)); return; } -- 1.7.1

1 0

[PATCH 1/4] [BUGFIX] pgcd(): avoid infinite loop if the first GCD candidate coincides with GCD
by Alexei Sheplyakov 17 May '10

17 May '10

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. Thanks to Aless Lasaruk for a bug report. --- check/Makefile.am | 4 ++++ check/pgcd_infinite_loop.cpp | 37 +++++++++++++++++++++++++++++++++++++ ginac/polynomial/pgcd.cpp | 2 -- 3 files changed, 41 insertions(+), 2 deletions(-) create mode 100644 check/pgcd_infinite_loop.cpp diff --git a/check/Makefile.am b/check/Makefile.am index 3751613..7aaed07 100644 --- a/check/Makefile.am +++ b/check/Makefile.am @@ -31,6 +31,7 @@ EXAMS = exam_paranoia \ exam_mod_gcd \ bugme_chinrem_gcd \ pgcd_relatively_prime_bug \ + pgcd_infinite_loop \ exam_cra TIMES = time_dennyfliegner \ @@ -259,6 +260,9 @@ bugme_chinrem_gcd_LDADD = ../ginac/libginac.la pgcd_relatively_prime_bug_SOURCES = pgcd_relatively_prime_bug.cpp pgcd_relatively_prime_bug_LDADD = ../ginac/libginac.la +pgcd_infinite_loop_SOURCES = pgcd_infinite_loop.cpp +pgcd_infinite_loop_LDADD = ../ginac/libginac.la + AM_CPPFLAGS = -I$(srcdir)/../ginac -I../ginac -DIN_GINAC CLEANFILES = exam.gar diff --git a/check/pgcd_infinite_loop.cpp b/check/pgcd_infinite_loop.cpp new file mode 100644 index 0000000..013b746 --- /dev/null +++ b/check/pgcd_infinite_loop.cpp @@ -0,0 +1,37 @@ +#include <iostream> +#include <string> +#include "ginac.h" +using namespace GiNaC; +using namespace std; + +static const string srep("\ +792*z^8*w^4*x^3*y^4*u^7 + 24*z^4*w^4*x^2*y^3*u^4 \ ++ 264*z^8*w^3*x^2*y^7*u^5 + 198*z^4*w^5*x^5*y*u^6 \ ++ 110*z^2*w^3*x^5*y^4*u^6 - 120*z^8*w*x^4*u^6 \ +- 480*z^5*w*x^4*y^6*u^8 - 720*z^7*x^3*y^3*u^7 \ ++ 165*z^4*w^2*x^4*y*u^5 + 450*z^8*w^6*x^2*y*u^8 \ ++ 40*z^2*w^3*x^3*y^3*u^6 - 288*z^7*w^2*x^3*y^6*u^6 \ ++ 250*z^6*w^4*x^2*y^4*u^8 + 576*z^7*w^7*x^2*y^4*u^8 \ +- 80*z^6*w^2*x^5*y^3*u^7 - 144*z^8*w^4*x^5*u^7 \ ++ 120*z^4*w*x^2*y^6*u^6 + 320*z^5*w^5*x^2*y^7*u^8 \ ++ 192*z^7*w^6*x*y^7*u^6 - 12*z^4*w^3*x^3*y^5*u^6 \ +- 36*z^4*w^4*x^4*y^2*u^8 + 72*z^4*w^5*x^3*u^6 \ +- 20*z^2*w^2*x^4*y^5*u^8 + 660*z^8*w*x^2*y^4*u^6 \ ++ 66*z^4*w^4*x^4*y^4*u^4 + 440*z^6*w^2*x^3*y^7*u^7 \ +- 30*z^4*w*x^3*y^2*u^7 - 48*z^8*w^3*x^4*y^3*u^5 \ ++ 72*z^6*w^2*x*y^6*u^4 - 864*z^7*w^3*x^4*y^3*u^8 \ ++ 480*z^7*w^4*x*y^4*u^7 + 60*z^4*w^2*x^2*u^5 \ ++ 375*z^8*w^3*x*y*u^7 + 150*z^8*w^5*x*y^4*u^6 \ ++ 180*z^6*x*y^3*u^5 + 216*z^6*w^3*x^2*y^3*u^6"); + +int main(int argc, char** argv) +{ + cout << "Checking for more pgcd() bugs (infinite loop) ... " << flush; + parser the_parser; + ex e = the_parser(srep); + const symbol x = ex_to<symbol>(the_parser.get_syms()["x"]); + ex g = gcd(e, e.diff(x)); + cout << "not found. " << flush; + cout << g << endl << flush; + return 0; +} diff --git a/ginac/polynomial/pgcd.cpp b/ginac/polynomial/pgcd.cpp index 0de0f70..fac3735 100644 --- a/ginac/polynomial/pgcd.cpp +++ b/ginac/polynomial/pgcd.cpp @@ -134,8 +134,6 @@ ex pgcd(const ex& A, const ex& B, const exvector& vars, const long p) const ex H_lcoeff = lcoeff_wrt(H, restvars); if (H_lcoeff.is_equal(lc_gcd)) { - if ((Hprev-H).expand().smod(pn).is_zero()) - continue; ex C /* primitive part of H */, contH /* dummy */; primpart_content(C, contH, H, vars, p); // Normalize GCD so that leading coefficient is 1 -- 1.7.1

1 0

[SCM] GiNaC -- a C++ library for symbolic computations branch, ginac_1-5, updated. release_1-4-0-232-g05f749a
by git＠ginac.de 13 May '10

13 May '10

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GiNaC -- a C++ library for symbolic computations". The branch, ginac_1-5 has been updated via 05f749ac2abb672f8e0a1cef938ea1e83e1255dc (commit) via 511764215de1756329e88c2628a4fd36e8277195 (commit) from 406f9f2022af2bcc55eea6dac7a5c5a500046f29 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 05f749ac2abb672f8e0a1cef938ea1e83e1255dc Author: Richard Kreckel <kreckel(a)ginac.de> Date: Thu May 13 22:54:52 2010 +0200 Fix memory leak in excompiler due to use of wrong operator delete. This was reported by Martin Ettl <ettl.martin(a)gmx.de>. commit 511764215de1756329e88c2628a4fd36e8277195 Author: Richard Kreckel <kreckel(a)ginac.de> Date: Thu May 13 18:30:40 2010 +0200 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. ----------------------------------------------------------------------- Summary of changes: check/exam_inifcns.cpp | 3 +++ check/exam_inifcns_nstdsums.cpp | 15 ++++++++------- check/exam_pseries.cpp | 3 +++ check/time_antipode.cpp | 1 + check/time_gammaseries.cpp | 4 ++-- ginac/excompiler.cpp | 4 ++-- ginsh/ginsh_parser.yy | 2 +- 7 files changed, 20 insertions(+), 12 deletions(-) hooks/post-receive -- GiNaC -- a C++ library for symbolic computations

1 0