February 2010 - GiNaC-devel

Release soon
by Jens Vollinga 24 Feb '10

24 Feb '10

Hi, I am going to make a release soon, but I'll wait if something is pending. Regards, Jens

1 0

[SCM] GiNaC -- a C++ library for symbolic computations branch, master, updated. release_1-4-0-204-g6afbb97
by git＠ginac.de 24 Feb '10

24 Feb '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 6afbb9793e359cf388462c471ea256a6662b0cd4 (commit) from 25c7a8c09f7db73b48675777aa805e788f2308be (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 6afbb9793e359cf388462c471ea256a6662b0cd4 Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue Feb 23 12:01:23 2010 +0200 pgcd(): detect relatively prime polynomials properly... ... so pgcd() doesn't loop forever any more. Division test does not handle relatively prime polynomials (because C = 1 divides any polynomial). So we should stop interpolation (and return gcd of contents) if we got relatively prime images (we should do that for efficiency reasons too). Thanks to Jörg Arndt for a bug report. ----------------------------------------------------------------------- Summary of changes: check/Makefile.am | 3 +++ check/pgcd_relatively_prime_bug.cpp | 31 +++++++++++++++++++++++++++++++ ginac/polynomial/pgcd.cpp | 4 ++-- 3 files changed, 36 insertions(+), 2 deletions(-) create mode 100644 check/pgcd_relatively_prime_bug.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-224-g630e59f
by git＠ginac.de 24 Feb '10

24 Feb '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 630e59f66af9fcebb56a442f3aef433b0cc1c0e0 (commit) from ce67a917331907288c6702b05e191722f4f0441b (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 630e59f66af9fcebb56a442f3aef433b0cc1c0e0 Author: Alexei Sheplyakov <alexei.sheplyakov(a)gmail.com> Date: Tue Feb 23 12:01:23 2010 +0200 pgcd(): detect relatively prime polynomials properly... ... so pgcd() doesn't loop forever any more. Division test does not handle relatively prime polynomials (because C = 1 divides any polynomial). So we should stop interpolation (and return gcd of contents) if we got relatively prime images (we should do that for efficiency reasons too). Thanks to Jörg Arndt for a bug report. (cherry picked from commit 6afbb9793e359cf388462c471ea256a6662b0cd4) ----------------------------------------------------------------------- Summary of changes: check/Makefile.am | 3 +++ check/pgcd_relatively_prime_bug.cpp | 31 +++++++++++++++++++++++++++++++ ginac/polynomial/pgcd.cpp | 4 ++-- 3 files changed, 36 insertions(+), 2 deletions(-) create mode 100644 check/pgcd_relatively_prime_bug.cpp hooks/post-receive -- GiNaC -- a C++ library for symbolic computations

1 0

[PATCH] [BUGFIX] pgcd(): detect relatively prime polynomials properly...
by Alexei Sheplyakov 23 Feb '10

23 Feb '10

... so pgcd() doesn't loop forever any more. Division test does not handle relatively prime polynomials (because C = 1 divides any polynomial). So we should stop interpolation (and return gcd of contents) if we got relatively prime images (we should do that for efficiency reasons too). Thanks to Jörg Arndt for a bug report. --- check/Makefile.am | 3 +++ check/pgcd_relatively_prime_bug.cpp | 31 +++++++++++++++++++++++++++++++ ginac/polynomial/pgcd.cpp | 4 ++-- 3 files changed, 36 insertions(+), 2 deletions(-) create mode 100644 check/pgcd_relatively_prime_bug.cpp diff --git a/check/Makefile.am b/check/Makefile.am index 5b9dd58..3751613 100644 --- a/check/Makefile.am +++ b/check/Makefile.am @@ -30,6 +30,7 @@ EXAMS = exam_paranoia \ exam_misc \ exam_mod_gcd \ bugme_chinrem_gcd \ + pgcd_relatively_prime_bug \ exam_cra TIMES = time_dennyfliegner \ @@ -255,6 +256,8 @@ time_parser_LDADD = ../ginac/libginac.la bugme_chinrem_gcd_SOURCES = bugme_chinrem_gcd.cpp 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 AM_CPPFLAGS = -I$(srcdir)/../ginac -I../ginac -DIN_GINAC diff --git a/check/pgcd_relatively_prime_bug.cpp b/check/pgcd_relatively_prime_bug.cpp new file mode 100644 index 0000000..1d4c287 --- /dev/null +++ b/check/pgcd_relatively_prime_bug.cpp @@ -0,0 +1,31 @@ +/** @file pgcd_relatively_prime_bug.cpp + * + * A program exposing historical bug in the pgcd() function. + */ +#include <string> +#include <iostream> +#include <utility> +#include "ginac.h" +using namespace std; +using namespace GiNaC; + +int main(int argc, char** argv) +{ + cout << "Checking for pgcd() bug regarding relatively prime polynomials: " << flush; + const symbol q("q"); + parser reader; + reader.get_syms().insert(make_pair(string("q"), q)); + + ex t = reader("-E20^16*E4^8*E5^8*E1^16*q^4" + "-(E10^24-E20^8*E5^16)*E4^16*E1^8" + "+E2^24*E20^16*E5^8*q^4"); + ex g = gcd(t.expand(), t.diff(q).expand()) - 1; + if (!g.is_zero()) { + cout << " oops!" << endl << + "** Error: should be 0, got " << g << endl << flush; + throw std::logic_error("gcd was miscalculated"); + } + cout << "not found" << endl << flush; + return 0; +} + diff --git a/ginac/polynomial/pgcd.cpp b/ginac/polynomial/pgcd.cpp index 6e5e6b2..ef3748d 100644 --- a/ginac/polynomial/pgcd.cpp +++ b/ginac/polynomial/pgcd.cpp @@ -121,6 +121,8 @@ 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) @@ -145,8 +147,6 @@ ex pgcd(const ex& A, const ex& B, const exvector& vars, const long p) if (divide_in_z_p(Aprim, C, dummy1, vars, p) && divide_in_z_p(Bprim, C, dummy2, vars, p)) return (cont_gcd*C).expand().smod(pn); - else if (img_gcd_deg == 0) - return cont_gcd; // else continue building the candidate } } while(true); -- 1.6.6.1

1 0

multivariate factorization (ginac/ginsh)
by Jens Vollinga 21 Feb '10

21 Feb '10

Hi Jörg, Am 21.02.2010 08:59, schrieb Joerg Arndt: > [could someone please forward to ginac-devel, I am > not subscribed there] I am also reading cln-list :-) > # but it appears to do multivariate factorization as well: yes it does. > # The following seems to take forever: > >> t; > -E20^16*E4^8*E5^8*E1^16*q^4-(E10^24-E20^8*E5^16)*E4^16*E1^8+E2^24*E20^16*E5^8*q^4 >> factor(t); > > # ctrl-C > ginsh 815.46s user 3.39s system 94% cpu 14:26.22 total > > > Is the latter a huge-ish task or does ginac have a > performance issue here? I ran the example and I get an exception! So, it seems there is a bug somewhere. I'll have a look at it. Regards, Jens

2 3