#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 | 1d84c4a9160533338cb19a8df2351cd0fc9d79d0
Dependencies: #17673 | 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)
> }}}
>
> We implement a `xgcd` for the `QuotientFields` category in order to fix
> that (there was a `gcd` here without a `xgcd`). We also check that for
> PID the `gcd` and `xgcd` agree by implementing a `_test_gcd_vs_xgcd`.
> With that branch
> {{{
> sage: xgcd(6/1,2/1)
> (2, 0, 1)
> sage: xgcd(5/2, 3/4)
> (1/4, -1/2, 2)
> }}}
> which is consistent with `gcd`.
>
> 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` (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`.
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])
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17671#comment:12>
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.
