Opened 3 years ago

Closed 3 years ago

#28297 closed enhancement (fixed)

Small optimizations to arithmetic in number fields of degree > 2

Reported by: mmezzarobba Owned by:
Priority: minor Milestone: sage-8.9
Component: performance Keywords:
Cc: Merged in:
Authors: Marc Mezzarobba, Michael Orlitzky Reviewers: Michael Orlitzky, Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: c71c660 (Commits, GitHub, GitLab) Commit: c71c660a3e5c89ea081ac8161a4ee8cb05bc6e79
Dependencies: Stopgaps:

Status badges

Description (last modified by mmezzarobba)

Micro-benchmark (maybe of limited relevance):

sage: NF.<a> = NumberField(x^7 + 2, embedding=QQbar(-2)^(1/7))
sage: b = ((-7*a^6 + 3*a^4 - 5*a^3 + 2*a^2 - 4)/42)^10
sage: c = ((-7*a^6 + 7*a^4 - 5*a^3 + 2*a^2 - 4)/56)^10

Before:

sage: %timeit b+c
The slowest run took 5.91 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 4.76 µs per loop

After:

sage: %timeit b+c
The slowest run took 8.70 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 3.34 µs per loop

There seem to be a lot more opportunities to further improve basic arithmetic operations by removing gcds at the right moment. Please feel free to hijack the ticket if you find the time and energy to have a look!

Change History (10)

comment:1 Changed 3 years ago by mmezzarobba

  • Branch set to public/ticket/28297-nfe
  • Commit set to 2c361d60beff36e1bb3ef7530be72a100818abd7
  • Description modified (diff)
  • Status changed from new to needs_review
  • Summary changed from A small optimization to arithmetic in number fields to A small optimization to arithmetic in number fields of degree > 2

New commits:

2c361d6trivial optimization in addition of num field elts

comment:2 Changed 3 years ago by git

  • Commit changed from 2c361d60beff36e1bb3ef7530be72a100818abd7 to c14daead9d7c25722c96c9b08476e36b5d8efdd5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c14daeatrivial opts in basic arithmetic with number field elements

comment:3 Changed 3 years ago by mmezzarobba

  • Description modified (diff)
  • Summary changed from A small optimization to arithmetic in number fields of degree > 2 to Small optimizations to arithmetic in number fields of degree > 2

comment:4 Changed 3 years ago by git

  • Commit changed from c14daead9d7c25722c96c9b08476e36b5d8efdd5 to 8f93f0a0101e22038333519c3d2c453e6cce7151

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8f93f0atrivial opts in basic arithmetic with number field elements

comment:5 Changed 3 years ago by mmezzarobba

Rebased.

comment:6 follow-up: Changed 3 years ago by mjo

  • Reviewers set to Michael Orlitzky
  • Status changed from needs_review to positive_review

Seems straightforward:

The addition to _reduce_c_() bails out early if the denominator is one because in that case there's nothing to do. The check is cheap and avoids several other function calls that do nothing when the denominator is one, so I believe it's an improvement on average.

The changes to _add_() and _sub_() are identical. We now pull out the GCD of the two denominators (which are smallish numbers) early, and it eventually cancels out. This would happen anyway when we call _reduce_c_() before returning, but at that point we would be cancelling the same GCD out of the relatively-largish product of the denominators. I have faith that doing it early at least makes things no worse, and your numbers show an improvement, so it's fine by me. (This also makes it more likely that we hit the new "fast return" in _reduce_c_().)

Could you please describe the changes in a bit more detail in the commit message? That's my only nitpick.

comment:7 Changed 3 years ago by git

  • Commit changed from 8f93f0a0101e22038333519c3d2c453e6cce7151 to c71c660a3e5c89ea081ac8161a4ee8cb05bc6e79
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. New commits:

c71c660trivial opts in basic arithmetic with number field elements

comment:8 in reply to: ↑ 6 Changed 3 years ago by mmezzarobba

  • Authors changed from Marc Mezzarobba to Marc Mezzarobba, Michael Orlitzky
  • Reviewers changed from Michael Orlitzky to Michael Orlitzky, Marc Mezzarobba
  • Status changed from needs_review to positive_review

Replying to mjo:

Could you please describe the changes in a bit more detail in the commit message? That's my only nitpick.

I've copied your detailed description (minus a few sentences) there. I hope that's okay.

Thank you for the review!

comment:9 Changed 3 years ago by mjo

Yes that's fine with me. You don't have to give me author credit for just describing what you did, but you're the boss =)

comment:10 Changed 3 years ago by vbraun

  • Branch changed from public/ticket/28297-nfe to c71c660a3e5c89ea081ac8161a4ee8cb05bc6e79
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.