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:  sage9.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 twogenerators 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 followup: ↓ 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