[SCM] GiNaC -- a C++ library for symbolic computations branch, master, updated. release_1-4-0-177-g3627c2c
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 3627c2c0f2fe8fe04816703c5fc6dad9c96fb0a6 (commit) via a3a0f8b23bb70802cb0fc952cafdc2223c892fe9 (commit) via 80b1c3e0ee0e465d56e5c76bef4e52ef2dbc5197 (commit) from b9dc3d71083fe1a2f90a34db24b57b06ad51ebde (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 3627c2c0f2fe8fe04816703c5fc6dad9c96fb0a6 Author: Alexei Sheplyakov <varg@metalica.kh.ua> Date: Fri Feb 6 08:57:32 2009 +0200 Fix chinese_remainder() so modular GCD actually works. commit a3a0f8b23bb70802cb0fc952cafdc2223c892fe9 Author: Jens Vollinga <jensv@balin.nikhef.nl> Date: Fri Feb 6 13:13:06 2009 +0100 Automake now needs to be version >=1.8. Older versions like 1.7.9 do not create the directory m4 in a VPATH build. commit 80b1c3e0ee0e465d56e5c76bef4e52ef2dbc5197 Author: Jens Vollinga <jensv@balin.nikhef.nl> Date: Thu Feb 5 10:54:21 2009 +0100 Renamed files *.tcc and *.hpp to *.h. ----------------------------------------------------------------------- Summary of changes: check/Makefile.am | 6 +++- check/bugme_chinrem_gcd.cpp | 32 ++++++++++++++++++++ check/{error_report.hpp => error_report.h} | 0 check/exam_cra.cpp | 2 +- check/exam_mod_gcd.cpp | 6 ++-- check/match_bug.cpp | 2 +- check/time_uvar_gcd.cpp | 8 ++-- configure.ac | 2 +- ginac/Makefile.am | 26 ++++++++-------- ginac/ginac.h | 4 +- ginac/parser/{debug.hpp => debug.h} | 0 ginac/parser/default_reader.tpl | 2 +- ginac/parser/lexer.cpp | 2 +- ginac/parser/{lexer.hpp => lexer.h} | 0 ginac/parser/parse_binop_rhs.cpp | 6 ++-- ginac/parser/parse_context.cpp | 2 +- .../parser/{parse_context.hpp => parse_context.h} | 0 ginac/parser/parser.cpp | 6 ++-- ginac/parser/{parser.hpp => parser.h} | 2 +- ginac/parser/parser_compat.cpp | 2 +- ginac/polynomial/collect_vargs.cpp | 2 +- ginac/polynomial/cra_garner.cpp | 2 +- ginac/polynomial/{cra_garner.hpp => cra_garner.h} | 0 ginac/polynomial/{debug.hpp => debug.h} | 0 ginac/polynomial/euclid_gcd_wrap.h | 6 ++-- ginac/polynomial/eval_uvar.h | 4 +- ginac/polynomial/{gcd_euclid.tcc => gcd_euclid.h} | 10 +++--- ginac/polynomial/gcd_uvar.cpp | 2 +- ginac/polynomial/heur_gcd_uvar.h | 8 ++-- ginac/polynomial/interpolate_padic_uvar.h | 2 +- ginac/polynomial/mod_gcd.cpp | 8 ++-- ginac/polynomial/{mod_gcd.hpp => mod_gcd.h} | 2 +- ginac/polynomial/{normalize.tcc => normalize.h} | 6 ++-- ginac/polynomial/poly_cra.h | 2 +- ginac/polynomial/prem_uvar.h | 6 ++-- ginac/polynomial/primes_factory.h | 2 +- ginac/polynomial/primpart_content.cpp | 2 +- ginac/polynomial/{remainder.tcc => remainder.h} | 8 ++-- .../polynomial/{ring_traits.hpp => ring_traits.h} | 0 ginac/polynomial/smod_helpers.h | 2 +- ginac/polynomial/sr_gcd_uvar.h | 6 ++-- ginac/polynomial/{upoly.hpp => upoly.h} | 4 +- ginac/polynomial/upoly_io.cpp | 4 +- ginac/polynomial/{upoly_io.hpp => upoly_io.h} | 2 +- 44 files changed, 118 insertions(+), 82 deletions(-) create mode 100644 check/bugme_chinrem_gcd.cpp rename check/{error_report.hpp => error_report.h} (100%) rename ginac/parser/{debug.hpp => debug.h} (100%) rename ginac/parser/{lexer.hpp => lexer.h} (100%) rename ginac/parser/{parse_context.hpp => parse_context.h} (100%) rename ginac/parser/{parser.hpp => parser.h} (98%) rename ginac/polynomial/{cra_garner.hpp => cra_garner.h} (100%) rename ginac/polynomial/{debug.hpp => debug.h} (100%) rename ginac/polynomial/{gcd_euclid.tcc => gcd_euclid.h} (84%) rename ginac/polynomial/{mod_gcd.hpp => mod_gcd.h} (88%) rename ginac/polynomial/{normalize.tcc => normalize.h} (96%) rename ginac/polynomial/{remainder.tcc => remainder.h} (96%) rename ginac/polynomial/{ring_traits.hpp => ring_traits.h} (100%) rename ginac/polynomial/{upoly.hpp => upoly.h} (98%) rename ginac/polynomial/{upoly_io.hpp => upoly_io.h} (92%) hooks/post-receive -- GiNaC -- a C++ library for symbolic computations
Dear Jens, On Fri, Feb 06, 2009 at 01:17:27PM +0100, Jens Vollinga wrote:
- Log ----------------------------------------------------------------- commit 3627c2c0f2fe8fe04816703c5fc6dad9c96fb0a6 Author: Alexei Sheplyakov <varg@metalica.kh.ua> Date: Fri Feb 6 08:57:32 2009 +0200
Fix chinese_remainder() so modular GCD actually works.
Although the patch I've posted looks `obviously correct' and happens to work for you (and Vladimir), it would be nice to wait for feedback from Richard (or someone else using 64-bit architecture) before committing it. Best regards, Alexei
Hi, Alexei Sheplyakov schrieb:
Although the patch I've posted looks `obviously correct' and happens to work for you (and Vladimir), it would be nice to wait for feedback from Richard (or someone else using 64-bit architecture) before committing it.
as you can see, commit 3627c2c0f2fe8fe04816703c5fc6dad9c96fb0a6 already exists ... I did read your remark
much more severe bug (in multivariate GCD code). I'll fix the test after I find out what is wrong with chinrem_gcd().
and are waiting with the release, of course, until this issue is settled. Regards, Jens
Hi, On Mon, Feb 09, 2009 at 11:08:49AM +0100, Jens Vollinga wrote:
I did read your remark
much more severe bug (in multivariate GCD code). I'll fix the test after I find out what is wrong with chinrem_gcd().
and are waiting with the release, of course, until this issue is settled.
On Mon, Feb 09, 2009 at 08:22:47PM +0100, Richard B. Kreckel wrote:
For the record, here's what I did: $ git checkout master~9 This left me with "HEAD is now at 45b1e47... Implement modular multivariate GCD (based on chinese remaindering algorithm)." I applied you "patch", made check and it hang at the same point that has been reported before by Jens and Vladimir on 32-bit systems.
Now I believe my theory and the fix for poly_cra() are correct. Please find the patch fixing the univarite GCD timing below. From: Alexei Sheplyakov <varg@metalica.kh.ua> Subject: [PATCH] Univariate GCD timing: use sr_gcd when appropriate. The benchmark consists of two parts: 1) timing of different GCD calculation methods (i.e. subresultant PRS, heuristic, chinese remaindering). 2) timing of different implementations of the same method. The purpose is to find out how (in)efficient GiNaC::ex is as a representation of (univariate) polynomials (as a side note, the result is a bit depressing -- using coefficient vector instead of GiNaC:ex makes GCD calculation 50x -- 1000x faster). Now GiNaC uses modular (chinese remaindering) GCD by default, so part 2) got broken, i.e. instead of (intended) timings a) (heuristic, GiNaC::ex) versus (heuristic, coefficient vector) b) (PRS, GiNaC::ex) versus (PRS, coefficient vector) one gets a') (heuristic, GiNaC::ex) versus (heuristic, coefficient vector) b') (chinese remaindering, GiNaC::ex) versus (PRS, coefficient vector) Set the gcd_options::use_sr_gcd to restore the meaning of the benchmark. Note: this patch does not affect the library proper. --- check/time_uvar_gcd.cpp | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-) diff --git a/check/time_uvar_gcd.cpp b/check/time_uvar_gcd.cpp index c65c515..fe75897 100644 --- a/check/time_uvar_gcd.cpp +++ b/check/time_uvar_gcd.cpp @@ -1780,7 +1780,8 @@ struct ex_sr_gcd_test const upoly& g_check; unsigned options; ex_sr_gcd_test(const ex& a_, const ex& b_, const upoly& g_) : - a(a_), b(b_), g(0), g_check(g_), options(gcd_options::no_heur_gcd) + a(a_), b(b_), g(0), g_check(g_), options(gcd_options::no_heur_gcd | + gcd_options::use_sr_gcd) { } inline void run() -- 1.5.6.5 Best regards, Alexei
Hi Alexei, Alexei Sheplyakov schrieb:
2) timing of different implementations of the same method. The purpose is to find out how (in)efficient GiNaC::ex is as a representation of (univariate) polynomials (as a side note, the result is a bit depressing -- using coefficient vector instead of GiNaC:ex makes GCD calculation 50x -- 1000x faster).
is this the difference between GiNaC::ex and non-GiNaC::ex access or between GiNaC::{mul,add} and std::vector representation? And is this difference for a dense or non-dense representation in a vector? Just curious. Maybe if automatic conversion between mul/add and a dedicated polynomial class is restricted to happen only for gcd calculations it is very beneficial. Regards, Jens
participants (3)
-
Alexei Sheplyakov
-
git＠ginac.de
-
Jens Vollinga