[GiNaC-devel] Univarite GCD timing correction
Alexei Sheplyakov
varg at metalica.kh.ua
Mon Feb 16 15:23:16 CET 2009
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 at 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 835 bytes
Desc: Digital signature
URL: <http://www.cebix.net/pipermail/ginac-devel/attachments/20090216/8ceb952f/attachment.sig>
More information about the GiNaC-devel
mailing list