[GiNaC-list] code: extended gcd

[Ralf Stephan]

> Maple:  gcdex
> CLN:    xgcd
> Pari:   bezout
> Mma:    ExtendedGCD
> MuPAD:  gcdex
> Singular: extgcd
> Lidia:  xgcd
> 
> @Ralf: Can you say anything about the uniqueness of the cofactors computed
> by your xgcd function?  I mean, when you have g==u*a+v*b you also have
> g==(u+b)*v+(v-a)*b and so on.  With integers it is trivial to normalize u
> and v, e.g. to the smallest possible absolute values.

You mean g==(u+b)*a+(v-a)*b, no I can't say anything about this, the
literature is mostly about integers, and I have not the background to
tackle it. BTW the Magma manual says


   Ch. 44 UNIVARIATE POLYNOMIAL RINGS 187

   Xgcd(f, g) XGCD(f, g)

   The extended greatest common divisor of polynomials f and g in a
   univariate polynomial ring

   P : the function returns polynomials c, a and b in P such that c is
   the GCD f and g (as defined in the function GreatestCommonDivisor),
   and a * f + b * g = c. The coefficient ring must be a field. Since the
   GCD c is unique, the multipliers a and b are unique if f and g are both
   non-zero.

   For polynomials over the rational field, a modular algorithm due to
   Allan Steel(unpublished) is used; over other fields the basic
   Euclidean algorithm is used.

So there is another algorithm to ponder...


ralf