Opened 3 years ago
Closed 16 months ago
#13628 closed task (fixed)
refactor xgcd
Reported by: | saraedum | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | trivial | Milestone: | sage-6.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 tscrim)
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 3 years ago by saraedum
- Status changed from new to needs_review
comment:2 Changed 3 years ago by saraedum
- Status changed from needs_review to needs_work
comment:3 Changed 3 years ago by saraedum
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=t-1,t^2-1 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=t-1,t^2-1 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 3 years ago by saraedum
- Status changed from needs_work to needs_review
Changed 3 years ago by saraedum
Changed 3 years ago by saraedum
identical to the previous patch — but the patchbot somehow didn't want to pick up the new patch
comment:6 Changed 3 years ago by tscrim
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 22 months ago by jdemeyer
- Milestone changed from sage-5.11 to sage-5.12
comment:8 Changed 17 months ago by vbraun
Please rebase...
comment:9 Changed 16 months ago by niles
- Branch set to u/niles/ticket/13628
- Created changed from 10/19/12 08:53:40 to 10/19/12 08:53:40
- Modified changed from 12/23/13 05:23:41 to 12/23/13 05:23:41
comment:10 Changed 16 months ago by niles
- Commit set to 5b6e9c677f7fe5b4e6a484953b8f8ce1b2ec16d0
comment:11 follow-up: ↓ 12 Changed 16 months ago by tscrim
- 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 16 months ago by niles
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 16 months ago by git
- Commit changed from 72a598ea4e767523cc843500388f758639daeba6 to 11bcbdbf7a8e32cea71b1de1eac7c0c67fbd64f8
Branch pushed to git repo; I updated commit sha1. New commits:
11bcbdb | Fixed failing doctests. |
comment:14 Changed 16 months ago by git
- 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 16 months ago by tscrim
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 16 months ago by vbraun_spam
- Milestone changed from sage-6.1 to sage-6.2
comment:17 Changed 16 months ago by niles
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 backtick-quoted 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 16 months ago by git
- 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 16 months ago by tscrim
- 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:20 Changed 16 months ago by niles
- Status changed from needs_review to positive_review
Looks good.
comment:21 Changed 16 months ago by vbraun
- Resolution set to fixed
- Status changed from positive_review to closed
I want to remove self from the docstrings.