Opened 10 years ago

Closed 9 years ago

#13441 closed task (fixed)

refactor gcd

Reported by: saraedum Owned by: AlexGhitza
Priority: trivial Milestone: sage-6.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:

Status badges

Description (last modified by 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.

Attachments (1)

trac_13441.patch (9.9 KB) - added by saraedum 10 years ago.

Download all attachments as: .zip

Change History (30)

comment:1 Changed 10 years ago by saraedum

  • Dependencies set to #13439

comment:2 Changed 10 years ago by 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.)

comment:3 Changed 10 years ago by saraedum

  • Dependencies changed from #13439 to #13439, #13438

comment:4 Changed 10 years ago by saraedum

  • Dependencies changed from #13439, #13438 to #13438

comment:5 Changed 10 years ago by saraedum

  • Dependencies #13438 deleted

comment:6 Changed 10 years ago by saraedum

  • Description modified (diff)

comment:7 Changed 10 years ago by saraedum

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

Last edited 10 years ago by saraedum (previous) (diff)

comment:8 Changed 10 years ago by saraedum

  • Status changed from new to needs_review

comment:9 Changed 10 years ago by roed

  • 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 follow-up: Changed 10 years ago by saraedum

  • 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 10 years ago by saraedum

  • Status changed from needs_review to needs_work

comment:12 in reply to: ↑ 10 Changed 10 years ago by 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.

comment:13 Changed 10 years ago by 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…

Last edited 10 years ago by saraedum (previous) (diff)

comment:14 Changed 10 years ago by saraedum

  • Status changed from needs_work to needs_review

comment:15 Changed 10 years ago by saraedum

  • Status changed from needs_review to needs_work

Changed 10 years ago by saraedum

comment:16 Changed 10 years ago by saraedum

  • Status changed from needs_work to needs_review

comment:17 Changed 10 years ago by saraedum

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

comment:18 Changed 10 years ago by tscrim

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 9 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:20 Changed 9 years ago by 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?

comment:21 Changed 9 years ago by 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.

comment:22 Changed 9 years ago by niles

  • 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 9 years ago by niles

  • Commit set to c3df98176643734dc7bdc95cc077ef02af274d3b

rebased and converted to git branch; no other changes


New commits:

c3df981Trac #13441: refactored gcd to not use _gcd calls anymore
Last edited 9 years ago by niles (previous) (diff)

comment:24 Changed 9 years ago by tscrim

  • Branch changed from u/niles/ticket/13441 to u/tscrim/ticket/13441
  • Commit changed from c3df98176643734dc7bdc95cc077ef02af274d3b to 7cdeebbb524ccfc00a9f38f3c8dcd1aa7ed901f3

New commits:

dc7f187Merge branch 'u/niles/ticket/13441' of trac.sagemath.org:sage into u/tscrim/ticket/13441
7cdeebbRemoved tab characters and some very minor review tweaks.

comment:25 follow-up: Changed 9 years ago by 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.

comment:26 in reply to: ↑ 25 Changed 9 years ago by 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?

comment:27 Changed 9 years ago by tscrim

  • Reviewers set to Niles Johnson, Travis Scrimshaw
  • Status changed from needs_review to positive_review

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

comment:28 Changed 9 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:29 Changed 9 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.