[GiNaC-list] code: extended gcd

[Richard B. Kreckel]

On Tue, 16 Nov 2004, Christian Bauer wrote:
> @Richy: Are we still using Maple naming conventions? Should this be called
>         gcdex()?

I don't see a reason why Maple naming conventions should be any better
than others.  If we've been following Maple naming conventions it's been
because we didn't know better.  Maple's argument ordering doesn't follow
any conventions either and fortunately we chose not to adopt it.  Well,
let's see how others call it:

Maple:  gcdex
        gcdex(A,B,x,'s','t').  Note that the signature is different,
        anyways.

CLN:    xgcd
        There is cl_I xgcd(const cl_I& a, const cl_I& b, cl_I* u, cl_I* v).
        Integers only!

Pari:   bezout
        After the B'ezout Identity.  The signature is: bezout(x,y): gives
        a 3-dimensional row vector [u,v,d] such that d=gcd(x,y) and
        u*x+v*y=d.

Mma:    ExtendedGCD
        That long name follows Mathematica's unique verbose naming
        convention.

MuPAD:  gcdex
        They copied all the conventions from Maple when they started with
        the whole system.


Singular: extgcd
        extgcd(x,y) returns a list of 3 objects of the same type as the
        type of the arguments.

Lidia:  xgcd
        But it's not the same as in CLN: they reverse (a,b) <-> (u,v):
        bigint xgcd(bigint& u, bigint& v, const bigint& a, const bigint& b)
        [shudder] Integers only!

...

That should be enough to give up looking for a consensus.

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

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