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
comment:2 follow-up: ↓ 3 Changed 5 years ago by
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).
- A course in computational number theory (Cohen)
g*r
,s
andt
whereg
is the GCD andr
the resultant, ands
andt
satisfyg*r = s*a+t*b
for inputsa
andb
.
- For softwares and libraries (inputs are two univariate polynomials
a
andb
over the integers):- Flint:
fmpz_poly_xgcd
computesr
,s
andt
wherer=res(a,b)
andr=s*a+t*b
; - NTL: idem Flint;
- Mathemagix: the
xgcd
-like function returns an error; - Maple17: the function
gcdex
works as ifa
andb
were defined over the rational numbers; - Mathematica (? tested via WolframAlpha): idem Maple17.
- Flint:
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: ↓ 4 Changed 5 years ago by
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
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 namefmpz_poly_xgcd
. This may look like nitpicking, but it's really not. The FLINT call is explicit that it's forfmpz_poly
: polynomials overZZ
. When you use the genericxgcd
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
- Component changed from PLEASE CHANGE to basic arithmetic
- Type changed from PLEASE CHANGE to defect
Wikipedia is formal about the definition of xgcd. But there is a mention of
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.