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.

[saraedum]

I want to remove self from the docstrings.

[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.

[saraedum]

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

[saraedum]

Apply only trac_13628.2.patch

[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.

[vbraun]

Please rebase...

[niles]

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]

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.

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

[git]

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

​11bcbdb

Fixed failing doctests.

[git]

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

​2e26b21

Fixed missed parenthesis for a tuple.

[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.

[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.

[git]

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

​5b3ee54

Fix typo and MATH docstrong.

[tscrim]

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.

[niles]

Looks good.