Le 26/01/2015 18:06, Vincent Delecroix a écrit :
2015-01-26 17:07 UTC+01:00, Jeroen Demeyer <jdeme...@cage.ugent.be>:
On 2015-01-26 14:22, Bruno Grenet wrote:
In the special case of univariate polynomials over ZZ, I think there are
two possibilities for xgcd:
- either xgcd(p,q) = (g,u,v) where g = gcd(p,q) = up+vq with u,v in
QQ[x];
- or xgcd(p,q) = (g×r, u, v) where g = gcd(p,q), r = res(p,q), g×r =
up+vq with u,v in ZZ[x].
More generally, Bézout coefficients seem to be usually defined only for
PID, and this motivates the first solution (in general, replace ZZ by a
UFD R and QQ by its field of fractions K). The second solution has the
advantage of staying in the same polynomial ring, and it has a clear
definition. I would go for the second solution, with an updated
documentation.
The second definition might be useful to have as algorithm, but I would
never call it xgcd(). Call it pseudo_xgcd() or resultant_xgcd().
I agree. But definitely distinct from the purpose of #17671. I opened
#17674 for that.
It seems that I am alone not agreeing, but let me just detail my arguments:
In the case of PID, the method `xgcd` returns something else than the
GCD, and not even an "extended GCD" (that does not exist). It returns
the Bézout identity (made of the GCD and the Bézout coefficients), and
the term "extended" (the "x" in "xgcd") refers to the "extended
Euclidean algorithm" and not to "extended GCD". Thus, for non-PIDs, the
method `xgcd` should still return the Bézout identity, which is defined
slightly differently. This is currently the case in Sage. I haven't
checked in other softwares, but I wouldn't be surprised that they have
the same convention (to be checked...).
Not having a `xgcd` method for polynomials over ZZ seems disturbing to
me, and I am not sure users would think to look to other names.
Another possibility would be to rename the `xgcd` method in all cases:
As I've written above, there is not such thing as an "extended GCD", so
the name is not a very good one in any case. Then one could use
`bezout_identity` or `bezout_triple` or something similar in all cases.
Cheers,
Bruno
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
