refactor gcd

[saraedum]

Currently, some classes define a _gcd method which is called by a gcd method of euclidean domain elements. Most elements already define gcd directly, and I see no real use in having this method in between.

The attached patch renames all _gcd methods to gcd and also streamlines the use of @coerce_binop on them.

This is similar to #13628.

[saraedum]

I also removed Polynomial_dense_mod_p's gcd since it cannot be called at all. (I'm running doctests now to verify this.)

[saraedum]

Removed Rational's gcd since it was not used anymore (rational numbers rely on QuotientFields?.ElementMethods?.gcd).

[roed]

My main concern is with a speed penalty in doing gcds for rationals, polynomial_integer_dense_ntl, etc. Have you compared the runtime of the gcds before and after your changes?

I agree that it's conceptually nicer.

[saraedum]

Without the patch I get:

sage: x,y=34912364,123324234
sage: timeit('x.gcd(y)')
625 loops, best of 3: 430 ns per loop
sage: x,y=234/234525,4324525/12351
sage: timeit('x.gcd(y)')
625 loops, best of 3: 11.5 µs per loop
sage: R.<T>=ZZ[]
sage: x,y=123*T^2+23424*T+1231,1231451*T^3+65*T^2+352*T+234251
sage: timeit('x.gcd(y)')
625 loops, best of 3: 6.06 µs per loop

With the patch:

sage: x,y=34912364,123324234
sage: timeit('x.gcd(y)')
625 loops, best of 3: 1.13 µs per loop
sage: x,y=234/234525,4324525/12351
sage: timeit('x.gcd(y)')
625 loops, best of 3: 14.1 µs per loop
sage: R.<T>=ZZ[]
sage: x,y=123*T^2+23424*T+1231,1231451*T^3+65*T^2+352*T+234251
sage: timeit('x.gcd(y)')
625 loops, best of 3: 6.21 µs per loop

So there is actually a speed penalty. This seems to be caused by a bug in coerce_binop:

sage: x.gcd
<sage.structure.element.NamedBinopMethod object at 0x1bc255f0>
sage: x.gcd
<sage.structure.element.NamedBinopMethod object at 0x1bc27290>

I'm looking into this.

[saraedum]

Replying to saraedum:

So there is actually a speed penalty. This seems to be caused by a bug in coerce_binop:

sage: x.gcd
<sage.structure.element.NamedBinopMethod object at 0x1bc255f0>
sage: x.gcd
<sage.structure.element.NamedBinopMethod object at 0x1bc27290>

This is just how decorators work on methods (if they don't do tricks like cached_method) - the __get__ has to create a new instance on every call.

[saraedum]

The speed problems seem to be resolved with the new patch:

Without the patch:

sage: x,y=34912364,123324234
sage: sage: sage: timeit('x.gcd(y)')
625 loops, best of 3: 427 ns per loop
sage: sage: R.<t>=PolynomialRing(GF(3),implementation="NTL")
sage: sage: x,y=t^2-1,t-1
sage: sage: sage: timeit('x.gcd(y)')
625 loops, best of 3: 35.5 µs per loop
age: sage: x,y=234/234525,4324525/12351
sage: sage: sage: timeit('x.gcd(y)')
625 loops, best of 3: 11.4 µs per loop
age: sage: R.<t> = PolynomialRing(ZZ,implementation="NTL")
sage: sage: x,y=t^2-1,t-1
sage: sage: sage: timeit('x.gcd(y)')
625 loops, best of 3: 17.8 µs per loop

With the patch:

sage: x,y=34912364,123324234
sage: sage: sage: timeit('x.gcd(y)')
625 loops, best of 3: 421 ns per loop
sage: R.<t>=PolynomialRing(GF(3),implementation="NTL")
sage: x,y=t^2-1,t-1
sage: sage: timeit('x.gcd(y)')
625 loops, best of 3: 32.7 µs per loop
sage: x,y=234/234525,4324525/12351
sage: sage: timeit('x.gcd(y)')
625 loops, best of 3: 11.5 µs per loop
sage: R.<t> = PolynomialRing(ZZ,implementation="NTL")
sage: x,y=t^2-1,t-1
sage: sage: timeit('x.gcd(y)')
625 loops, best of 3: 17.3 µs per loop

Let's see what the patchbot thinks about it…

[saraedum]

The patchbot reported some problems with rational numbers. These should be fixed now.

[tscrim]

Minor issue: the INPUT: bullets are indented one to many times (they should be level with the triple quotes and INPUT:). Thanks.

[pbruin]

A question: is there a good technical reason to make gcd() a method of EuclideanDomains.ElementMethods instead of EuclideanDomainElement? To me it seems conceptually preferable to keep it a method of EuclideanDomainElement.

To be honest, I don't really see the (mathematical) point of having a category of Euclidean domains, at least not in its current form. There would presumably need to be some condition requiring the "quotient and remainder" function to be compatible with morphisms in this category, and even then I wonder how useful it would be. Again, maybe there is a good technical reason to have such a category?

[vbraun]

IMHO this is precisely what the category framework is about. We aren't talking about mathematical categories, but at non-inheritance framework to ensure consistency. There isn't much use in a stand-alone EuclideanDomains category, but it is definitely useful as a subcategory that you can slap on whenever you have a euclidean domain.

Alas, the patch does not apply to Sage 6. Please rebase.

[niles]

rebased and converted to git branch; no other changes

---

New commits:

​c3df981

Trac #13441: refactored gcd to not use _gcd calls anymore

[tscrim]

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.

[tscrim]

I made some review tweaks to the documentation (and it's now based off develop), so if you're happy with my changes, then go ahead and set this to positive review.

[niles]

Replying to tscrim:

I made some review tweaks to the documentation (and it's now based off develop)

thanks!

if you're happy with my changes, then go ahead and set this to positive review.

I haven't reviewed this patch, just converted it to a git branch so I can work with it. I can see that it seems to work, and that the documentation builds correctly and looks good. But I haven't looked more closely at it; in particular I haven't verified the timing results. I do give a positive review to your changes -- are you giving positive review to the earlier parts of the patch/branch?

[tscrim]

I double-checked and I am getting the same times (up to noise), so then it's positive review all around.