- GiNaC-devel - ginac.de

[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

[SCM] GiNaC -- a C++ library for symbolic computations branch, master, updated. release_1-4-0-213-gb604136
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, master has been updated via b604136850dac1fa8016623349061f2a3b0085be (commit) via 93d02d3b90587f38cbc33cf25ee89795c415574c (commit) from e22d2ed95925d870876c4fcd922ea2a9cfdbdab1 (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 b604136850dac1fa8016623349061f2a3b0085be 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 93d02d3b90587f38cbc33cf25ee89795c415574c 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

[SCM] GiNaC -- a C++ library for symbolic computations branch, master, updated. release_1-4-0-211-ge22d2ed
by git＠ginac.de 27 Apr '10

27 Apr '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 e22d2ed95925d870876c4fcd922ea2a9cfdbdab1 (commit) from 8a30acc990818792ec4e8f8f4d48f5dd8286dbed (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 e22d2ed95925d870876c4fcd922ea2a9cfdbdab1 Author: Richard Kreckel <kreckel(a)ginac.de> Date: Tue Apr 27 22:44:35 2010 +0200 Fix weird ctor invocation syntax. This patch is required for GCC-4.5. ----------------------------------------------------------------------- Summary of changes: ginac/function.pl | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) 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-230-g406f9f2
by git＠ginac.de 27 Apr '10

27 Apr '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 406f9f2022af2bcc55eea6dac7a5c5a500046f29 (commit) from c48424be67d8c6b05b0e040acd49b3e904acf6f9 (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 406f9f2022af2bcc55eea6dac7a5c5a500046f29 Author: Richard Kreckel <kreckel(a)ginac.de> Date: Tue Apr 27 22:44:35 2010 +0200 Fix weird ctor invocation syntax. This patch is required for GCC-4.5. ----------------------------------------------------------------------- Summary of changes: ginac/function.pl | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) hooks/post-receive -- GiNaC -- a C++ library for symbolic computations

1 0

GiNaC release 1.5.7
by Jens Vollinga 29 Mar '10

29 Mar '10

Hi everybody, GiNaC 1.5.7 is out and available. The changes are: * Fixed a bug in the GCD code (infinite loop in pgcd()). * Fixed a bug in atan2() (division by zero error for atan2(x,0) if x is a negative and composite term). * Products now correctly set info_flags::negative and info_flags::negint. As always, this release can be downloaded from http://www.ginac.de/Download.html Best wishes, Jens

1 0

[SCM] GiNaC -- a C++ library for symbolic computations tag, release_1-5-7, created. release_1-4-0-229-gc48424b
by git＠ginac.de 29 Mar '10

29 Mar '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 tag, release_1-5-7 has been created at c48424be67d8c6b05b0e040acd49b3e904acf6f9 (commit) - Log ----------------------------------------------------------------- commit c48424be67d8c6b05b0e040acd49b3e904acf6f9 Author: Jens Vollinga <jensv(a)nikhef.nl> Date: Mon Mar 29 02:34:52 2010 +0200 Preparing for release 1.5.7. ----------------------------------------------------------------------- hooks/post-receive -- GiNaC -- a C++ library for symbolic computations

1 0