refactor xgcd

[saraedum]

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.

Depends on #13441
Depends on #13438

Component: basic arithmetic

Author: Julian Rueth

Branch/Commit: u/tscrim/ticket/13628 @ 5b3ee54

Reviewer: Niles Johnson, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/13628

[saraedum]

comment:2

I want to remove self from the docstrings.

[saraedum]

comment:3

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.

[saraedum]

Attachment: trac_13628.patch.gz

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

[saraedum]

comment:5

Attachment: trac_13628.2.patch.gz

Apply only trac_13628.2.patch

[tscrim]

comment:6

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.

[vbraun]

comment:8

Please rebase...

[nilesjohnson]

Branch: u/niles/ticket/13628

[nilesjohnson]

Commit: 5b6e9c6

[nilesjohnson]

comment:10

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:

c3df981	Trac #13441: refactored gcd to not use _gcd calls anymore
5b6e9c6	Trac #13628: refactored xgcd to not use _xgcd calls anymore.

[tscrim]

Changed commit from 5b6e9c6 to 72a598e

[tscrim]

Changed branch from u/niles/ticket/13628 to u/tscrim/ticket/13628

[tscrim]

comment:11

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.

[nilesjohnson]

comment:12

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)
**********************************************************************

[sagetrac-git]

Changed commit from 72a598e to 11bcbdb

[sagetrac-git]

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

11bcbdb

Fixed failing doctests.

[sagetrac-git]

Changed commit from 11bcbdb to 2e26b21

[sagetrac-git]

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

2e26b21

Fixed missed parenthesis for a tuple.

[tscrim]

comment:15

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.

[nilesjohnson]

comment:17

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.

[sagetrac-git]

Changed commit from 2e26b21 to 5b3ee54

[sagetrac-git]

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

5b3ee54

Fix typo and MATH docstrong.

[tscrim]

Reviewer: Niles Johnson, Travis Scrimshaw

[tscrim]

comment:19

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.

[nilesjohnson]

comment:20

Looks good.