[GiNaC-list] code: extended gcd

Christian Bauer Christian.Bauer at uni-mainz.de
Mon Nov 8 15:34:04 CET 2004


Hi!

On Mon, Nov 08, 2004 at 12:45:41PM +0100, Ralf Stephan wrote:
> To declare something as cofactor does not mean it is. What the function
> returns does NOT satisfy the usual cofactor equation
> 
>          gcd(a,b) = ca*a + cb*b.

These are not the cofactors (at least, I've never seen the quantities from
this equation referred to as "cofactors"). The cofactors in GiNaC's gcd()
are defined by

  a = ca*gcd(a,b)  ->  ca = a/gcd(a,b)
  b = cb*gcd(a,b)  ->  cb = b/gcd(a,b)

Like many other things in GiNaC, this follows the behavior of Maple.

What you want (the solutions to s,t in gcd(a,b)=s*a+t*b) is indeed something
entirely different, and computed by a different algorithm (gcdex() in Maple).

> Vide my earlier example, or a = (x-1)(x+1), b = (x-1)^3 which should
> give ca = (3-x)/4 and cb = 1/4. But it gives ca = (1-x)^2, cb = 1+x.

(It actually gives ca=1+x, cb=(1-x)^2.)

Bye,
Christian

-- 
  / Physics is an algorithm
\/ http://www.uni-mainz.de/~bauec002/



More information about the GiNaC-list mailing list