[GiNaC-list] gcd: wrong sign of cofactor (heur_gcd is broken?)

[Jens Vollinga]

Hi,

thanks for the patch! It has been applied.

Regards,
Jens

On Tue, Mar 22, 2005 at 03:33:08PM +0300, Sheplyakov Alexei wrote:
> Hello!
> 
> This simple program fails:
> 
> #include <iostream>
> #include <stdexcept>
> #include <cassert>
> #include <ginac/ginac.h>
> using namespace std;
> using namespace GiNaC;
> 
> int main(int argc, char** argv)
> {
> 	symbol x("x");
> 	symbol y("y");
> 		ex a = pow(x,2) - pow(y,2);
> 		ex b = pow(x,4) - pow(y, 4);
> 		ex ca, cb;
> 		cout << "GCD(" << a << ", " << b << ") = ";
> 		ex ab_gcd =  gcd(a, b, &ca, &cb, false);
> 		cout << ab_gcd << endl;
> 		assert((a-ca*ab_gcd).expand().is_zero());
> 		assert((b-cb*ab_gcd).expand().is_zero());
> 		return 0;
> }
> 
> Documentation (normal.cpp:1256) says 
> \begin{quote}
> /*
>  * Compute GCD (Greatest Common Divisor) of multivariate 
>  * polynomials a(X) and b(X) in Z[X]. Optionally also compute 
>  * the cofactors of a and b, defined by a = ca * gcd(a, b)
>  * and b = cb * gcd(a, b).
>  */
> \end{quote}
> 
> so this behaviour is probably a bug.
> 
> I've got a patch to fix it (see attachment #1), but I'm not sure if
> it is correct.
> 
> Relevant part of gdb session is attached too.
> 
> P.S.
> 
> I use GiNaC 1.3.1 from CVS, g++-3.4 from Debian testing.
> 
> 
> --
> Best regards,
>   Alexei