[GiNaC-devel] [PATCH] gcd: fix heuristics to chose main variable properly

[Sheplyakov Alexei]

Hi,

On Mon, Nov 20, 2006 at 09:02:23PM +0100, bernard.parisse wrote:
> >Heuristic code in gcd [very] often makes bad choice of the main variable.
> >In particular, if one of polynomials (say, p2) does not contain
> >the variable x which _is contained_ in another one (say, p1), than
> >gcd(p1, p2) will use such a variable as a main, so subsequent calculation
> >becomes unnecessary complicated. Fixing this substantially improves worst
> >case performance (less than minute versus infinity).
> > 
> in this case, you should compute the content with respect to x of p1
> and then the gcd of the content with p2.

The old code used to do so:

if (var->deg_a == 0) {
	ex bex_u, bex_c, bex_p;
	bex.unitcontprim(x, bex_u, bex_c, bex_p);
	ex g = gcd(aex, bex_c, ca, cb, false);
	if (cb)
		*cb *= bex_u*bex_p;
	return g;
	} else if (var->deg_b == 0) {
		ex aex_u, aex_c, aex_p;
		aex.unitcontprim(x, aex_u, aex_c, aex_p);
		ex g = gcd(aex_c, bex, ca, cb, false);
		if (ca)
			*ca *= aex_u * aex_p;
		return g;
	}

This is exactly what leads to inferior performance (example is
attached).

> A good candidate for the gcd will be the gcd of p2 with a random
> integer linear combination of the coeffs of p1 with respect to x.

I'm not trying to provide a [better] guess. The point is to prevent
the code from making particulary bad ones, especially when polynomials
in question are relatively prime.

> Anyway, heuristic gcd is most of the time not a good choice if there
> are more than a few variables. Modular gcd is in my experience faster
> (and this is theoretically also true).

I agree with you completely. But unfortunately GiNaC is not well suited
for doing modular arithmetics [yet] :(

Best regards,
 Alexei

-- 
All science is either physics or stamp collecting.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: thepoly_another.cpp.gz
Type: application/octet-stream
Size: 1037 bytes
Desc: not available
URL: <http://www.ginac.de/pipermail/ginac-devel/attachments/20061121/b63e1092/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
URL: <http://www.ginac.de/pipermail/ginac-devel/attachments/20061121/b63e1092/attachment.sig>