Opened 7 years ago
Closed 6 years ago
#13628 closed task (fixed)
refactor xgcd
Reported by:  saraedum  Owned by:  AlexGhitza 

Priority:  trivial  Milestone:  sage6.2 
Component:  basic arithmetic  Keywords:  
Cc:  Merged in:  
Authors:  Julian Rueth  Reviewers:  Niles Johnson, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  u/tscrim/ticket/13628 (Commits)  Commit:  5b3ee54bb662e494a7a93f6729b20713412ad6ca 
Dependencies:  #13441, #13438  Stopgaps: 
Description (last modified by )
Currently, some classes define a _xgcd method which is called by a xgcd method of euclidean domain elements. Most elements already define xgcd directly, and I see no real use in having this method in between.
The attached patch renames all _xgcd methods to xgcd and also streamlines the use of @coerce_binop on them.
This is similar to #13441.
Attachments (2)
Change History (23)
comment:1 Changed 7 years ago by
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:3 Changed 7 years ago by
The patch introduces a speed penalty for integers. Therefore I left the method _xgcd
in for integers for places where this really matters. The following timings are without/with
the patch applied.
sage: x,y=3,21 sage: timeit('x.xgcd(y)') 625 loops, best of 3: 986 ns/1.56 µs per loop sage: timeit('x._xgcd(y)') 625 loops, best of 3: 713 ns/704 ns per loop sage: x,y=1/3,1/21 sage: timeit('x.xgcd(y)') 625 loops, best of 3:  /7.92 µs per loop sage: R.<t> = QQbar[] sage: x,y=t1,t^21 sage: timeit('x.xgcd(y)') 125 loops, best of 3: 1.17 ms/1.18 ms per loop sage: R.<t> = PolynomialRing(GF(3),implementation="NTL") sage: x,y=t1,t^21 sage: timeit('x.xgcd(y)') 625 loops, best of 3: 80 µs/80.9 µs per loop
Notice that there was no xgcd
method for rational numbers before since it was defined only for PrincipalIdealDomainElement
which FieldElement
does not inherit from.
Also the docstring for Integers talked about some weirdness
that was actually not present anymore. I checked all combinations of integers between 20 and 20 but could not find a single case where the output of xgcd without the minimal
option produced something really surprising.
If the patchbot does not find any problems, then this is ready for review.
comment:4 Changed 7 years ago by
 Status changed from needs_work to needs_review
Changed 7 years ago by
Changed 7 years ago by
identical to the previous patch — but the patchbot somehow didn't want to pick up the new patch
comment:6 Changed 7 years ago by
Two minor things; the INPUT:
and OUTPUT:
blocks in the fields.py
and polynomial_modn_dense_ntl.pyx
files are indented one to many times and I prefer to have tuples in parenthesis (r, s, t)
in the documentation. Thanks.
comment:7 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:8 Changed 6 years ago by
Please rebase...
comment:9 Changed 6 years ago by
 Branch set to u/niles/ticket/13628
 Created changed from 10/19/12 15:53:40 to 10/19/12 15:53:40
 Modified changed from 12/23/13 13:23:41 to 12/23/13 13:23:41
comment:10 Changed 6 years ago by
 Commit set to 5b6e9c677f7fe5b4e6a484953b8f8ce1b2ec16d0
comment:11 followup: ↓ 12 Changed 6 years ago by
 Branch changed from u/niles/ticket/13628 to u/tscrim/ticket/13628
 Commit changed from 5b6e9c677f7fe5b4e6a484953b8f8ce1b2ec16d0 to 72a598ea4e767523cc843500388f758639daeba6
The branch I've attached is based on develop
(and fixes the merge conflcit) and has some minor docstring review changes. If you're happy with my changes, then go ahead and set this to positive review.
New commits:
dc7f187  Merge branch 'u/niles/ticket/13441' of trac.sagemath.org:sage into u/tscrim/ticket/13441

7cdeebb  Removed tab characters and some very minor review tweaks.

3a1f217  Merge branch 'u/niles/ticket/13628' of trac.sagemath.org:sage into u/tscrim/ticket/13628

72a598e  Some minor docstring review changes.

comment:12 in reply to: ↑ 11 Changed 6 years ago by
Replying to tscrim:
The branch I've attached is based on
develop
(and fixes the merge conflcit) and has some minor docstring review changes.
Got some failing doctests here; if you fix them I can give positive review to your changes. (You could also change tuples in the documentation to use parentheses, which I like too.) Are you giving positive review to the other parts of the patch?
sage t long src/sage/rings/polynomial/polynomial_quotient_ring.py ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 254, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic Failed example: [s for s in dir(Q.category().element_class) if not s.startswith('_')] Expected: ['cartesian_product', 'is_idempotent', 'is_one', 'lift', 'xgcd'] Got: ['cartesian_product', 'is_idempotent', 'is_one', 'is_unit', 'lift'] ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 267, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic Failed example: [s for s in dir(Q.category().element_class) if not s.startswith('_')] Expected: ['cartesian_product', 'gcd', 'is_idempotent', 'is_one', 'is_unit', 'lcm', 'lift'] Got: ['cartesian_product', 'gcd', 'is_idempotent', 'is_one', 'is_unit', 'lcm', 'lift', 'xgcd'] ********************************************************************** sage t long src/sage/rings/integer.pyx ********************************************************************** File "src/sage/rings/integer.pyx", line 5390, in sage.rings.integer.Integer._xgcd Failed example: 5._xgcd(0, minimal=True) Exception raised: Traceback (most recent call last): ... TypeError: bad operand type for unary : 'tuple' ********************************************************************** sage t long src/sage/rings/arith.py ********************************************************************** File "src/sage/rings/arith.py", line 1886, in sage.rings.arith.xgcd Failed example: g, a, b = xgcd(5/1, 7/1); g, a, b Expected: (1, 3, 2) Got: (1, 1/5, 0) **********************************************************************
comment:13 Changed 6 years ago by
 Commit changed from 72a598ea4e767523cc843500388f758639daeba6 to 11bcbdbf7a8e32cea71b1de1eac7c0c67fbd64f8
Branch pushed to git repo; I updated commit sha1. New commits:
11bcbdb  Fixed failing doctests.

comment:14 Changed 6 years ago by
 Commit changed from 11bcbdbf7a8e32cea71b1de1eac7c0c67fbd64f8 to 2e26b217df37fd113cbdde00a090d4601f508786
Branch pushed to git repo; I updated commit sha1. New commits:
2e26b21  Fixed missed parenthesis for a tuple.

comment:15 Changed 6 years ago by
Fixed. The first two just had to be changed due to the method's definition moving locations. The third was an order of operations mistake. The last one, because 5/1
and 7/1
are in \QQ
, I think is okay to change it to the output rather than treating them as integers which was what was previously happening.
comment:16 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:17 Changed 6 years ago by
Thanks for the fixes. Checking the documentation, I found a couple of problems in sage.rings.Integer
:
 There is a typo "NOET" in the docstring for
xgcd
 The MATH blocks for the Bezout identity in
xgcd
and_xgcd
each have an extra\rm
: The syntax\mbox{\rm self}
renders as "\rm self". Probably the block can just be replaced with a backtickquoted line, since that's what's used in other xgcd docsstrings:``g = s * self + t * n``
\rm self
occurs in another line of_xgcd
docstring, but since this is an underscore method I don't know how to check the built docstring. Maybe remove it since the other\rm
's caused trouble, but this is a minor point since no regular user will view the built documentation for_xgcd
.
Everything else looks fine, so I can give positive review to the reviewer patch when these (admittedly annoying) details are fixed.
comment:18 Changed 6 years ago by
 Commit changed from 2e26b217df37fd113cbdde00a090d4601f508786 to 5b3ee54bb662e494a7a93f6729b20713412ad6ca
Branch pushed to git repo; I updated commit sha1. New commits:
5b3ee54  Fix typo and MATH docstrong.

comment:19 Changed 6 years ago by
 Description modified (diff)
 Reviewers set to Niles Johnson, Travis Scrimshaw
Whoops, that typo was from me. I've fixed the MATH block to use \mathrm{self}
. If that works for you, then you can set this to positive review. Thanks.
comment:21 Changed 6 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
I want to remove
self
from the docstrings.