#17674: xgcd is badly named on non PID domains
---------------------------------+------------------------
Reporter: vdelecroix | Owner:
Type: PLEASE CHANGE | Status: new
Priority: major | Milestone: sage-6.5
Component: PLEASE CHANGE | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+------------------------
Comment (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.
--
Ticket URL: <http://trac.sagemath.org/ticket/17674#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
