Opened 22 months ago

Closed 6 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)

trac_13628.patch (18.1 KB) - added by saraedum 21 months ago.
trac_13628.2.patch (18.1 KB) - added by saraedum 21 months ago.
identical to the previous patch — but the patchbot somehow didn't want to pick up the new patch

Download all attachments as: .zip

Change History (23)

comment:1 Changed 22 months ago by saraedum

  • Status changed from new to needs_review

comment:2 Changed 21 months ago by saraedum

  • Status changed from needs_review to needs_work

I want to remove self from the docstrings.

Last edited 21 months ago by saraedum (previous) (diff)

comment:3 Changed 21 months 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 21 months ago by saraedum

  • Status changed from needs_work to needs_review

Changed 21 months ago by saraedum

Changed 21 months ago by saraedum

identical to the previous patch — but the patchbot somehow didn't want to pick up the new patch

comment:5 Changed 21 months ago by saraedum

  • Description modified (diff)

Apply only trac_13628.2.patch

comment:6 Changed 20 months 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 12 months ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:8 Changed 7 months ago by vbraun

Please rebase...

comment:9 Changed 6 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 6 months ago by niles

  • Commit set to 5b6e9c677f7fe5b4e6a484953b8f8ce1b2ec16d0

rebased to sage 6.0 and converted to git branch; no other changes

merges cleanly in local repository in spite of what trac says


New commits:

c3df981Trac #13441: refactored gcd to not use _gcd calls anymore
5b6e9c6Trac #13628: refactored xgcd to not use _xgcd calls anymore.

comment:11 follow-up: Changed 6 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:

dc7f187Merge branch 'u/niles/ticket/13441' of trac.sagemath.org:sage into u/tscrim/ticket/13441
7cdeebbRemoved tab characters and some very minor review tweaks.
3a1f217Merge branch 'u/niles/ticket/13628' of trac.sagemath.org:sage into u/tscrim/ticket/13628
72a598eSome minor docstring review changes.

comment:12 in reply to: ↑ 11 Changed 6 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 6 months ago by git

  • Commit changed from 72a598ea4e767523cc843500388f758639daeba6 to 11bcbdbf7a8e32cea71b1de1eac7c0c67fbd64f8

Branch pushed to git repo; I updated commit sha1. New commits:

11bcbdbFixed failing doctests.

comment:14 Changed 6 months ago by git

  • Commit changed from 11bcbdbf7a8e32cea71b1de1eac7c0c67fbd64f8 to 2e26b217df37fd113cbdde00a090d4601f508786

Branch pushed to git repo; I updated commit sha1. New commits:

2e26b21Fixed missed parenthesis for a tuple.

comment:15 Changed 6 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 6 months ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:17 Changed 6 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 6 months ago by git

  • Commit changed from 2e26b217df37fd113cbdde00a090d4601f508786 to 5b3ee54bb662e494a7a93f6729b20713412ad6ca

Branch pushed to git repo; I updated commit sha1. New commits:

5b3ee54Fix typo and MATH docstrong.

comment:19 Changed 6 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 6 months ago by niles

  • Status changed from needs_review to positive_review

Looks good.

comment:21 Changed 6 months ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.