Sage: Ticket #13441: refactor gcd
https://trac.sagemath.org/ticket/13441
<p>
Currently, some classes define a <code>_gcd</code> method which is called by a <code>gcd</code> method of euclidean domain elements. Most elements already define <code>gcd</code> directly, and I see no real use in having this method in between.
</p>
<p>
The attached patch renames all <code>_gcd</code> methods to <code>gcd</code> and also streamlines the use of <code>@coerce_binop</code> on them.
</p>
<p>
This is similar to <a class="closed ticket" href="https://trac.sagemath.org/ticket/13628" title="task: refactor xgcd (closed: fixed)">#13628</a>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13441
Trac 1.1.6saraedumSat, 08 Sep 2012 22:10:35 GMTdependencies set
https://trac.sagemath.org/ticket/13441#comment:1
https://trac.sagemath.org/ticket/13441#comment:1
<ul>
<li><strong>dependencies</strong>
set to <em>#13439</em>
</li>
</ul>
TicketsaraedumSat, 08 Sep 2012 22:11:57 GMT
https://trac.sagemath.org/ticket/13441#comment:2
https://trac.sagemath.org/ticket/13441#comment:2
<p>
I also removed <code>Polynomial_dense_mod_p</code>'s gcd since it cannot be called at all. (I'm running doctests now to verify this.)
</p>
TicketsaraedumSat, 08 Sep 2012 22:34:55 GMTdependencies changed
https://trac.sagemath.org/ticket/13441#comment:3
https://trac.sagemath.org/ticket/13441#comment:3
<ul>
<li><strong>dependencies</strong>
changed from <em>#13439</em> to <em>#13439, #13438</em>
</li>
</ul>
TicketsaraedumWed, 26 Sep 2012 15:15:08 GMTdependencies changed
https://trac.sagemath.org/ticket/13441#comment:4
https://trac.sagemath.org/ticket/13441#comment:4
<ul>
<li><strong>dependencies</strong>
changed from <em>#13439, #13438</em> to <em>#13438</em>
</li>
</ul>
TicketsaraedumWed, 26 Sep 2012 15:16:17 GMTdependencies deleted
https://trac.sagemath.org/ticket/13441#comment:5
https://trac.sagemath.org/ticket/13441#comment:5
<ul>
<li><strong>dependencies</strong>
<em>#13438</em> deleted
</li>
</ul>
TicketsaraedumFri, 19 Oct 2012 15:54:05 GMTdescription changed
https://trac.sagemath.org/ticket/13441#comment:6
https://trac.sagemath.org/ticket/13441#comment:6
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13441?action=diff&version=6">diff</a>)
</li>
</ul>
TicketsaraedumSat, 20 Oct 2012 19:59:03 GMT
https://trac.sagemath.org/ticket/13441#comment:7
https://trac.sagemath.org/ticket/13441#comment:7
<p>
Removed Rational's gcd since it was not used anymore (rational numbers rely on <code>QuotientFields.ElementMethods.gcd</code>).
</p>
TicketsaraedumSat, 20 Oct 2012 23:42:30 GMTstatus changed
https://trac.sagemath.org/ticket/13441#comment:8
https://trac.sagemath.org/ticket/13441#comment:8
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketroedWed, 24 Oct 2012 09:01:14 GMTstatus changed
https://trac.sagemath.org/ticket/13441#comment:9
https://trac.sagemath.org/ticket/13441#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
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?
</p>
<p>
I agree that it's conceptually nicer.
</p>
TicketsaraedumWed, 14 Nov 2012 18:13:44 GMTstatus changed
https://trac.sagemath.org/ticket/13441#comment:10
https://trac.sagemath.org/ticket/13441#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Without the patch I get:
</p>
<pre class="wiki">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
</pre><p>
With the patch:
</p>
<pre class="wiki">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
</pre><p>
So there is actually a speed penalty. This seems to be caused by a bug in <code>coerce_binop</code>:
</p>
<pre class="wiki">sage: x.gcd
<sage.structure.element.NamedBinopMethod object at 0x1bc255f0>
sage: x.gcd
<sage.structure.element.NamedBinopMethod object at 0x1bc27290>
</pre><p>
I'm looking into this.
</p>
TicketsaraedumWed, 14 Nov 2012 18:13:53 GMTstatus changed
https://trac.sagemath.org/ticket/13441#comment:11
https://trac.sagemath.org/ticket/13441#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketsaraedumThu, 15 Nov 2012 13:09:12 GMT
https://trac.sagemath.org/ticket/13441#comment:12
https://trac.sagemath.org/ticket/13441#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13441#comment:10" title="Comment 10">saraedum</a>:
</p>
<blockquote class="citation">
<p>
So there is actually a speed penalty. This seems to be caused by a bug in <code>coerce_binop</code>:
</p>
<pre class="wiki">sage: x.gcd
<sage.structure.element.NamedBinopMethod object at 0x1bc255f0>
sage: x.gcd
<sage.structure.element.NamedBinopMethod object at 0x1bc27290>
</pre></blockquote>
<p>
This is just how decorators work on methods (if they don't do tricks like cached_method) - the <code>__get__</code> has to create a new instance on every call.
</p>
TicketsaraedumThu, 15 Nov 2012 14:50:19 GMT
https://trac.sagemath.org/ticket/13441#comment:13
https://trac.sagemath.org/ticket/13441#comment:13
<p>
The speed problems seem to be resolved with the new patch:
</p>
<p>
Without the patch:
</p>
<pre class="wiki">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
</pre><p>
With the patch:
</p>
<pre class="wiki">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
</pre><p>
Let's see what the patchbot thinks about it…
</p>
TicketsaraedumThu, 15 Nov 2012 14:50:32 GMTstatus changed
https://trac.sagemath.org/ticket/13441#comment:14
https://trac.sagemath.org/ticket/13441#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketsaraedumSun, 18 Nov 2012 20:44:06 GMTstatus changed
https://trac.sagemath.org/ticket/13441#comment:15
https://trac.sagemath.org/ticket/13441#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketsaraedumSun, 18 Nov 2012 21:14:16 GMTattachment set
https://trac.sagemath.org/ticket/13441
https://trac.sagemath.org/ticket/13441
<ul>
<li><strong>attachment</strong>
set to <em>trac_13441.patch</em>
</li>
</ul>
TicketsaraedumSun, 18 Nov 2012 21:15:58 GMTstatus changed
https://trac.sagemath.org/ticket/13441#comment:16
https://trac.sagemath.org/ticket/13441#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketsaraedumSun, 18 Nov 2012 21:16:46 GMT
https://trac.sagemath.org/ticket/13441#comment:17
https://trac.sagemath.org/ticket/13441#comment:17
<p>
The patchbot reported some problems with rational numbers. These should be fixed now.
</p>
TickettscrimSun, 25 Nov 2012 08:03:38 GMT
https://trac.sagemath.org/ticket/13441#comment:18
https://trac.sagemath.org/ticket/13441#comment:18
<p>
Minor issue: the <code>INPUT:</code> bullets are indented one to many times (they should be level with the triple quotes and <code>INPUT:</code>). Thanks.
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/13441#comment:19
https://trac.sagemath.org/ticket/13441#comment:19
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketpbruinTue, 13 Aug 2013 19:26:31 GMT
https://trac.sagemath.org/ticket/13441#comment:20
https://trac.sagemath.org/ticket/13441#comment:20
<p>
A question: is there a good technical reason to make <code>gcd()</code> a method of <code>EuclideanDomains.ElementMethods</code> instead of <code>EuclideanDomainElement</code>? To me it seems conceptually preferable to keep it a method of <code>EuclideanDomainElement</code>.
</p>
<p>
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?
</p>
TicketvbraunMon, 23 Dec 2013 13:22:51 GMT
https://trac.sagemath.org/ticket/13441#comment:21
https://trac.sagemath.org/ticket/13441#comment:21
<p>
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.
</p>
<p>
Alas, the patch does not apply to Sage 6. Please rebase.
</p>
TicketnilesMon, 27 Jan 2014 21:25:55 GMTchangetime, time changed; branch set
https://trac.sagemath.org/ticket/13441#comment:22
https://trac.sagemath.org/ticket/13441#comment:22
<ul>
<li><strong>changetime</strong>
changed from <em>12/23/13 13:22:51</em> to <em>12/23/13 13:22:51</em>
</li>
<li><strong>branch</strong>
set to <em>u/niles/ticket/13441</em>
</li>
<li><strong>time</strong>
changed from <em>09/08/12 22:09:15</em> to <em>09/08/12 22:09:15</em>
</li>
</ul>
TicketnilesMon, 27 Jan 2014 21:26:56 GMTcommit set
https://trac.sagemath.org/ticket/13441#comment:23
https://trac.sagemath.org/ticket/13441#comment:23
<ul>
<li><strong>commit</strong>
set to <em>c3df98176643734dc7bdc95cc077ef02af274d3b</em>
</li>
</ul>
<p>
rebased and converted to git branch; no other changes
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c3df98176643734dc7bdc95cc077ef02af274d3b"><span class="icon"></span>c3df981</a></td><td><code>Trac #13441: refactored gcd to not use _gcd calls anymore</code>
</td></tr></table>
TickettscrimThu, 30 Jan 2014 16:44:46 GMTcommit, branch changed
https://trac.sagemath.org/ticket/13441#comment:24
https://trac.sagemath.org/ticket/13441#comment:24
<ul>
<li><strong>commit</strong>
changed from <em>c3df98176643734dc7bdc95cc077ef02af274d3b</em> to <em>7cdeebbb524ccfc00a9f38f3c8dcd1aa7ed901f3</em>
</li>
<li><strong>branch</strong>
changed from <em>u/niles/ticket/13441</em> to <em>u/tscrim/ticket/13441</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=dc7f18794477deba0f58b89b8df7700cc5e932a4"><span class="icon"></span>dc7f187</a></td><td><code>Merge branch 'u/niles/ticket/13441' of trac.sagemath.org:sage into u/tscrim/ticket/13441</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7cdeebbb524ccfc00a9f38f3c8dcd1aa7ed901f3"><span class="icon"></span>7cdeebb</a></td><td><code>Removed tab characters and some very minor review tweaks.</code>
</td></tr></table>
TickettscrimThu, 30 Jan 2014 16:45:25 GMT
https://trac.sagemath.org/ticket/13441#comment:25
https://trac.sagemath.org/ticket/13441#comment:25
<p>
I made some review tweaks to the documentation (and it's now based off <code>develop</code>), so if you're happy with my changes, then go ahead and set this to positive review.
</p>
TicketnilesThu, 30 Jan 2014 18:06:18 GMT
https://trac.sagemath.org/ticket/13441#comment:26
https://trac.sagemath.org/ticket/13441#comment:26
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13441#comment:25" title="Comment 25">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I made some review tweaks to the documentation (and it's now based off <code>develop</code>)
</p>
</blockquote>
<p>
thanks!
</p>
<blockquote class="citation">
<p>
if you're happy with my changes, then go ahead and set this to positive review.
</p>
</blockquote>
<p>
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?
</p>
TickettscrimThu, 30 Jan 2014 20:18:13 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/13441#comment:27
https://trac.sagemath.org/ticket/13441#comment:27
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Niles Johnson, Travis Scrimshaw</em>
</li>
</ul>
<p>
I double-checked and I am getting the same times (up to noise), so then it's positive review all around.
</p>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/13441#comment:28
https://trac.sagemath.org/ticket/13441#comment:28
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketvbraunSun, 02 Feb 2014 20:33:46 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/13441#comment:29
https://trac.sagemath.org/ticket/13441#comment:29
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
Ticket