Opened 10 months ago
Closed 10 months ago
#32615 closed enhancement (fixed)
Faster arithmetic with function field ideals
Reported by: | klee | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.5 |
Component: | algebra | Keywords: | |
Cc: | Merged in: | ||
Authors: | Kwankyu Lee | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | 0a77fa5 (Commits, GitHub, GitLab) | Commit: | 0a77fa52ca71ec76aca7ad9a7867b66828e6c761 |
Dependencies: | Stopgaps: |
Description (last modified by )
We make ideal arithmetic faster for ideals with two-generators representation.
sage: K.<x> = FunctionField(GF(2)); _.<Y> = K[] ....: L.<y> = K.extension(Y^7 - x^3*Y - x) ....: O = L.maximal_order() ....: I = O.ideal(y) ....: J = O.ideal(x + y) sage: def naive_power(i, n): ....: j = i ....: for s in range(n - 1): ....: j *= i ....: return j ....: sage: n = 100 sage: i = I / J sage: %timeit naive_power(i, n) 683 ms ± 8.82 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) sage: %timeit i^n 34.3 ms ± 454 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) sage: p, q = i.gens_two() sage: %timeit naive_power(i, n) # faster multiplication 147 ms ± 4.08 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) sage: %timeit i^n # faster powering 16.2 ms ± 149 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) sage: naive_power(i, n) == i^n True
Change History (11)
comment:1 Changed 10 months ago by
- Branch set to u/klee/32615
comment:2 Changed 10 months ago by
- Commit set to a16530020d7b48e53616880f4987139d1fac749c
comment:3 Changed 10 months ago by
- Status changed from new to needs_review
comment:4 follow-up: ↓ 8 Changed 10 months ago by
- Reviewers set to Travis Scrimshaw
One trivial little change:
def _gens_two(self): - """ + r"""
Once done, you can set a positive review on my behalf.
I do find this line
if len(self._gens_two.cache) == 2:
to be a little strange though.
comment:5 Changed 10 months ago by
- Commit changed from a16530020d7b48e53616880f4987139d1fac749c to 5d190dd754444367f9728bc24d0f1616502aa3a2
Branch pushed to git repo; I updated commit sha1. New commits:
5d190dd | Use raw docstring to prevent invalid escape warning
|
comment:6 Changed 10 months ago by
- Description modified (diff)
comment:7 Changed 10 months ago by
- Commit changed from 5d190dd754444367f9728bc24d0f1616502aa3a2 to 0a77fa52ca71ec76aca7ad9a7867b66828e6c761
Branch pushed to git repo; I updated commit sha1. New commits:
0a77fa5 | Drop use of _gens_two.cache
|
comment:8 in reply to: ↑ 4 Changed 10 months ago by
Replying to tscrim:
Sorry for the mess. I somehow lost a commit that I thought I uploaded.
One trivial little change:
def _gens_two(self): - """ + r"""Once done, you can set a positive review on my behalf.
Done now.
I do find this line
if len(self._gens_two.cache) == 2:to be a little strange though.
I had deleted this in the lost commit. Now done again.
I will wait for a green bot. Thank you for quick review.
comment:9 Changed 10 months ago by
Thanks. Sounds good. Green bot => positive review.
comment:10 Changed 10 months ago by
- Status changed from needs_review to positive_review
comment:11 Changed 10 months ago by
- Branch changed from u/klee/32615 to 0a77fa52ca71ec76aca7ad9a7867b66828e6c761
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Speed up ideal multiplication