Simplify __invert__ for polynomial quotient ring element #39402
Conversation
|
Documentation preview for this PR (built with commit 9f0b2c3; changes) is ready! 🎉 |
|
@user202729 I'm curious if this change has any performance impact. Would you mind posting a before/after |
|
That's a good question… on the other hand we can argue On the other hand, what happened previously is that they both have different supported/unsupported cases (e.g. previously There's the caveat of what to do with inexact rings… we have to adopt one option or the other either way. |
|
From my reading of this you added some extra checking in I would like to see before/after Additionally, your PR description mentions that you fixed a few bugs with this PR. Please add tests covering those bugs if you haven't yet, and add a pointer to this PR in the explanation of those tests (i.e. "See :issue: |
There is no linked issue or discussion in your PR description. Not sure if you meant to link something or if you accidentally checked the box out of habit. |
|
Not exactly bug, just missing feature — that previously Also, I don't think there's runtime overhead of passing between the Python–Cython boundary, except for what is already there in Python interpreter. Timing result: Setup code: sage: R.<x> = GF(5)[]
....: S = R.quotient(x^3+1)
sage: s_element = S(x+2)
....: r_element = x+2
....: modulus = x^3+1Before the PR: sage: %timeit ~s_element
11.9 μs ± 341 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit r_element.inverse_mod(modulus)
4.73 μs ± 185 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)After the PR: sage: %timeit ~s_element
9.72 μs ± 261 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit r_element.inverse_mod(modulus)
4.81 μs ± 267 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)So… Reasonable explanation why |
|
Great! Looks good to me. The |
sagemathgh-39402: Simplify __invert__ for polynomial quotient ring element Previously `__invert__` uses `xgcd`, while the method `inverse_mod` already exists, it's duplication of code. Besides, while simplifying this some missing features in `inverse_mod` is uncovered. ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. --> - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have created tests covering the changes. - [x] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on. For example, --> <!-- - sagemath#12345: short description why this is a dependency --> <!-- - sagemath#34567: ... --> URL: sagemath#39402 Reported by: user202729 Reviewer(s):
sagemathgh-39402: Simplify __invert__ for polynomial quotient ring element Previously `__invert__` uses `xgcd`, while the method `inverse_mod` already exists, it's duplication of code. Besides, while simplifying this some missing features in `inverse_mod` is uncovered. ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. --> - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have created tests covering the changes. - [x] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on. For example, --> <!-- - sagemath#12345: short description why this is a dependency --> <!-- - sagemath#34567: ... --> URL: sagemath#39402 Reported by: user202729 Reviewer(s):
sagemathgh-39402: Simplify __invert__ for polynomial quotient ring element Previously `__invert__` uses `xgcd`, while the method `inverse_mod` already exists, it's duplication of code. Besides, while simplifying this some missing features in `inverse_mod` is uncovered. ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. --> - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have created tests covering the changes. - [x] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on. For example, --> <!-- - sagemath#12345: short description why this is a dependency --> <!-- - sagemath#34567: ... --> URL: sagemath#39402 Reported by: user202729 Reviewer(s):
sagemathgh-39402: Simplify __invert__ for polynomial quotient ring element Previously `__invert__` uses `xgcd`, while the method `inverse_mod` already exists, it's duplication of code. Besides, while simplifying this some missing features in `inverse_mod` is uncovered. ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. --> - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have created tests covering the changes. - [x] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on. For example, --> <!-- - sagemath#12345: short description why this is a dependency --> <!-- - sagemath#34567: ... --> URL: sagemath#39402 Reported by: user202729 Reviewer(s):
Previously
__invert__usesxgcd, while the methodinverse_modalready exists, it's duplication of code. Besides, while simplifying this some missing features ininverse_modis uncovered.📝 Checklist
⌛ Dependencies