Small optimizations to arithmetic in number fields of degree > 2

[mezzarobba]

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!

Component: performance

Author: Marc Mezzarobba, Michael Orlitzky

Branch/Commit: c71c660

Reviewer: Michael Orlitzky, Marc Mezzarobba

Issue created by migration from https://trac.sagemath.org/ticket/28297

[mezzarobba]

Commit: 2c361d6

[mezzarobba]

New commits:

2c361d6

trivial optimization in addition of num field elts

[mezzarobba]

Branch: public/ticket/28297-nfe

[sagetrac-git]

Changed commit from 2c361d6 to c14daea

[sagetrac-git]

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

c14daea

trivial opts in basic arithmetic with number field elements

[sagetrac-git]

Changed commit from c14daea to 8f93f0a

[sagetrac-git]

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

8f93f0a

trivial opts in basic arithmetic with number field elements

[mezzarobba]

comment:5

Rebased.

[orlitzky]

Reviewer: Michael Orlitzky

[orlitzky]

comment:6

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.

[sagetrac-git]

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

c71c660

trivial opts in basic arithmetic with number field elements

[sagetrac-git]

Changed commit from 8f93f0a to c71c660

[mezzarobba]

Changed author from Marc Mezzarobba to Marc Mezzarobba, Michael Orlitzky

[mezzarobba]

comment:8

Replying to @orlitzky:

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!

[mezzarobba]

Changed reviewer from Michael Orlitzky to Michael Orlitzky, Marc Mezzarobba

[orlitzky]

comment:9

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 =)

[vbraun]

Changed branch from public/ticket/28297-nfe to c71c660