Opened 5 years ago

Last modified 5 years ago

#17674 new defect

xgcd is badly named on non PID domains

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.5
Component: basic arithmetic Keywords:
Cc: jdemeyer, bruno Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Over non PID domains, the method xgcd might not (and can not in general) return the gcd as its first argument

sage: x = polygen(ZZ)
sage: (x+2).gcd(x+4)  # no common factor but...
1
sage: (x+2).xgcd(x+4) # ... the ideal (x+2, x+4) is not principal
(2, -1, 1)

See this sage-devel thread where it was suggested to change the method name to pseudo_xgcd or _resultant_xgcd.

See also #17671 that fix some compatibility issues for gcd/xgcd over PID.

Change History (5)

comment:1 Changed 5 years ago by vdelecroix

Wikipedia is formal about the definition of xgcd. But there is a mention of

as + bt = Res(a,b)

in the section Polynomial extended Euclidean algorithm. See also the page on Bézout identity

magma defines xgcd only for univariate polynomials over fields or residue class ring with prime modulus.

comment:2 follow-up: Changed 5 years ago by bruno

Let me repeat and extend as a comment my remarks on sage-devel, concerning the "literature":

  • In almost all books in which I've checked, the extended Euclidean algorithm is only defined for polynomials over fields, and not over rings. This books include
    • Modern Computer Algebra (von zur Gathen and Gerhard);
    • The Art of Computer Programming: Semi-Numerical Algorithms (Knuth);
    • A Computational Introduction to Number Theory and Algebra (Shoup);
    • Fundamental problems in algorithmic algebra (Yap).
    The exception is in
    • A course in computational number theory (Cohen)
    where there is a mention (as a remark and and exercise) of the extended Euclidean Algorithm in the case of polynomials over UFDs, and the algorithm is suppose to return g*r, s and t where g is the GCD and r the resultant, and s and t satisfy g*r = s*a+t*b for inputs a and b.
  • For softwares and libraries (inputs are two univariate polynomials a and b over the integers):
    • Flint: fmpz_poly_xgcd computes r, s and t where r=res(a,b) and r=s*a+t*b;
    • NTL: idem Flint;
    • Mathemagix: the xgcd-like function returns an error;
    • Maple17: the function gcdex works as if a and b were defined over the rational numbers;
    • Mathematica (? tested via WolframAlpha): idem Maple17.

Now for my opinion:

  • My preferred solution is the one chosen by Flint and NTL, keeping the name xgcd;
  • If the consensus is to change the name, I would be greatly in favor of a name beginning with xgcd_... for completion considerations.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 5 years ago by jdemeyer

Replying to bruno:

  • My preferred solution is the one chosen by Flint and NTL, keeping the name xgcd;

FLINT does not use the name xgcd, it uses the name fmpz_poly_xgcd. This may look like nitpicking, but it's really not. The FLINT call is explicit that it's for fmpz_poly: polynomials over ZZ. When you use the generic xgcd name to mean both the "real" xgcd and the "fake" xgcd-times-resultant depending on the input, that's confusing.

comment:4 in reply to: ↑ 3 Changed 5 years ago by bruno

Replying to jdemeyer:

Replying to bruno:

  • My preferred solution is the one chosen by Flint and NTL, keeping the name xgcd;

FLINT does not use the name xgcd, it uses the name fmpz_poly_xgcd. This may look like nitpicking, but it's really not. The FLINT call is explicit that it's for fmpz_poly: polynomials over ZZ. When you use the generic xgcd name to mean both the "real" xgcd and the "fake" xgcd-times-resultant depending on the input, that's confusing.

In Sage you have the object-oriented syntax object.method() while in Flint there is some kind of naming convention type_function(). And you have fmpz_poly_xgcd exactly in the same way as you have fmpz_xgcd or fmpq_poly_xgcd, so one could argue, in the same way as you argue for the xgcd function in Sage, that a user expects these functions to implement the same mathematical function in the three cases. I am not sure (even if you think so) that the situation in Sage is much more confusing than the situation in Flint. Actually, I do not think it is really confusing in any case.

comment:5 Changed 5 years ago by rws

  • Component changed from PLEASE CHANGE to basic arithmetic
  • Type changed from PLEASE CHANGE to defect
Note: See TracTickets for help on using tickets.