[GiNaC-list] code: extended gcd

[Richard B. Kreckel]

Hi!

On Wed, 17 Nov 2004, Ralf Stephan wrote:
> > @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,

If that turns out to be undetermined, it should just be documented as
such.

>                                                                  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.

As it stands, that last sentence is not correct.  To see that, just drop
any two elements of any integral domain in a and b and try shifting them
according to above equation.  Maybe there is some other way to "normalize"
u and v to the most simple form?  Or maybe that is a non-issue for some
reason we don't see?

>    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...

...not unless Allan shares some of his insights with us.   :-)

Regards
     -richy.
-- 
Richard B. Kreckel
<http://www.ginac.de/~kreckel/>