#17671: gcd and xgcd over fields, PID and UFD
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.5
Component: basic arithmetic | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/17671 | c6db5f832b23d29026019de5306472a25e591279
Dependencies: #17673, #17675 | Stopgaps:
-------------------------------------+-------------------------------------
Description changed by vdelecroix:
Old description:
> As reported on [https://groups.google.com/forum/#!topic/sage-
> support/AYDqdxy5fTw sage-support], gcd and xgcd disagree on fraction
> fields
> {{{
> sage: gcd(6/1,2/1)
> 2
> sage: xgcd(6/1,2/1)
> (1, 1/6, 0)
> }}}
>
> In this ticket we:
> 1. Ensure that `gcd` and `xgcd` are compatible over quotient fields by
> implementing the `xgcd` in the appropriate place. In particular, with
> that branch we have
> {{{
> sage: xgcd(6/1,2/1)
> (2, 0, 1)
> sage: xgcd(5/2, 3/4)
> (1/4, -1/2, 2)
> }}}
> 2. We fix the `xgcd` for trivial cases in
> `rings.polynomial.polynomial_element_generic.Polynomial_generic_field` in
> order that `gcd` and `xgcd` agree for them.
> 3. We introduce a generic test `_test_gcd_vs_xgcd` in the category
> `PrincipalIdealDomains` to ensure the compatibility of `gcd` and `xgcd`.
>
> QUESTIONS:
>
> 1. In the previous implementation of gcd in `sage.categories.fields`
> there is a backward compatibility weirdness
> {{{
> sage: gcd(2.0, 4.0)
> 2
> sage: gcd(2.0, 4.0).parent()
> Integer Ring
> }}}
> For the moment, I propagated this to `lcm` and `xgcd`.
>
> 2. There is a method `xgcd` implemented for univariate polynomial over
> ZZ. ~~This is not a proper name since it has nothing to do with `gcd`~~
> This might not be the best name since the first term is not the gcd in
> general (see [https://groups.google.com/forum/#!topic/sage-
> devel/JV8fCPUqTzo this sage-devel thread])
New description:
As reported on [https://groups.google.com/forum/#!topic/sage-
support/AYDqdxy5fTw sage-support], gcd and xgcd disagree on fraction
fields
{{{
sage: gcd(6/1,2/1)
2
sage: xgcd(6/1,2/1)
(1, 1/6, 0)
}}}
In this ticket we:
1. Ensure that `gcd` and `xgcd` are compatible over quotient fields by
implementing the `xgcd` in the appropriate place. In particular, with that
branch we have
{{{
sage: xgcd(6/1,2/1)
(2, 0, 1)
sage: xgcd(5/2, 3/4)
(1/4, -1/2, 2)
}}}
2. We fix the `xgcd` for trivial cases in
`rings.polynomial.polynomial_element_generic.Polynomial_generic_field` in
order that `gcd` and `xgcd` agree for them.
3. We introduce a generic test `_test_gcd_vs_xgcd` in the category
`PrincipalIdealDomains` to ensure the compatibility of `gcd` and `xgcd`.
4. Modify the previous behavior for real numbers (which was present
because of mysterious backward compatibility reasons)
{{{
sage: gcd(2.0, 4.0)
2
sage: gcd(2.0, 4.0).parent()
Integer Ring
}}}
Now we have
{{{
sage: gcd(2.0, 4.0)
1.00000000000000
sage: gcd(2.0, 4.0).parent()
Real Field with 53 bits of precision
}}}
Note:
There is a method `xgcd` implemented for univariate polynomial over ZZ.
~~This is not a proper name since it has nothing to do with `gcd`~~ This
might not be the best name since the first term is not the gcd in general
(see [https://groups.google.com/forum/#!topic/sage-devel/JV8fCPUqTzo this
sage-devel thread] and #17674)
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17671#comment:20>
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.
