Opened 9 years ago
Closed 8 years ago
#13441 closed task (fixed)
refactor gcd
Reported by:  saraedum  Owned by:  AlexGhitza 

Priority:  trivial  Milestone:  sage6.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/13441 (Commits, GitHub, GitLab)  Commit:  7cdeebbb524ccfc00a9f38f3c8dcd1aa7ed901f3 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Attachments (1)
Change History (30)
comment:1 Changed 9 years ago by
 Dependencies set to #13439
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
 Dependencies changed from #13439 to #13439, #13438
comment:4 Changed 9 years ago by
 Dependencies changed from #13439, #13438 to #13438
comment:5 Changed 9 years ago by
 Dependencies #13438 deleted
comment:6 Changed 9 years ago by
 Description modified (diff)
comment:7 Changed 9 years ago by
Removed Rational's gcd since it was not used anymore (rational numbers rely on QuotientFields.ElementMethods.gcd
).
comment:8 Changed 9 years ago by
 Status changed from new to needs_review
comment:9 Changed 9 years ago by
 Status changed from needs_review to needs_info
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.
comment:10 followup: ↓ 12 Changed 9 years ago by
 Status changed from needs_info to needs_review
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.
comment:11 Changed 9 years ago by
 Status changed from needs_review to needs_work
comment:12 in reply to: ↑ 10 Changed 9 years ago by
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.
comment:13 Changed 9 years ago by
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^21,t1 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^21,t1 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^21,t1 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^21,t1 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…
comment:14 Changed 9 years ago by
 Status changed from needs_work to needs_review
comment:15 Changed 9 years ago by
 Status changed from needs_review to needs_work
Changed 9 years ago by
comment:16 Changed 9 years ago by
 Status changed from needs_work to needs_review
comment:17 Changed 9 years ago by
The patchbot reported some problems with rational numbers. These should be fixed now.
comment:18 Changed 9 years ago by
Minor issue: the INPUT:
bullets are indented one to many times (they should be level with the triple quotes and INPUT:
). Thanks.
comment:19 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:20 Changed 8 years ago by
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?
comment:21 Changed 8 years ago by
IMHO this is precisely what the category framework is about. We aren't talking about mathematical categories, but at noninheritance framework to ensure consistency. There isn't much use in a standalone 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.
comment:22 Changed 8 years ago by
 Branch set to u/niles/ticket/13441
 Created changed from 09/08/12 22:09:15 to 09/08/12 22:09:15
 Modified changed from 12/23/13 13:22:51 to 12/23/13 13:22:51
comment:23 Changed 8 years ago by
 Commit set to c3df98176643734dc7bdc95cc077ef02af274d3b
rebased and converted to git branch; no other changes
New commits:
c3df981  Trac #13441: refactored gcd to not use _gcd calls anymore

comment:24 Changed 8 years ago by
 Branch changed from u/niles/ticket/13441 to u/tscrim/ticket/13441
 Commit changed from c3df98176643734dc7bdc95cc077ef02af274d3b to 7cdeebbb524ccfc00a9f38f3c8dcd1aa7ed901f3
comment:25 followup: ↓ 26 Changed 8 years ago by
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.
comment:26 in reply to: ↑ 25 Changed 8 years ago by
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?
comment:27 Changed 8 years ago by
 Reviewers set to Niles Johnson, Travis Scrimshaw
 Status changed from needs_review to positive_review
I doublechecked and I am getting the same times (up to noise), so then it's positive review all around.
comment:28 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:29 Changed 8 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
I also removed
Polynomial_dense_mod_p
's gcd since it cannot be called at all. (I'm running doctests now to verify this.)