#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:

Status badges

Description (last modified by klee)

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 klee

  • Authors set to Kwankyu Lee
  • Branch set to u/klee/32615

comment:2 Changed 10 months ago by git

  • Commit set to a16530020d7b48e53616880f4987139d1fac749c

Branch pushed to git repo; I updated commit sha1. New commits:

a165300Speed up ideal multiplication

comment:3 Changed 10 months ago by klee

  • Status changed from new to needs_review

comment:4 follow-up: Changed 10 months ago by tscrim

  • 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 git

  • Commit changed from a16530020d7b48e53616880f4987139d1fac749c to 5d190dd754444367f9728bc24d0f1616502aa3a2

Branch pushed to git repo; I updated commit sha1. New commits:

5d190ddUse raw docstring to prevent invalid escape warning

comment:6 Changed 10 months ago by klee

  • Description modified (diff)

comment:7 Changed 10 months ago by git

  • Commit changed from 5d190dd754444367f9728bc24d0f1616502aa3a2 to 0a77fa52ca71ec76aca7ad9a7867b66828e6c761

Branch pushed to git repo; I updated commit sha1. New commits:

0a77fa5Drop use of _gens_two.cache

comment:8 in reply to: ↑ 4 Changed 10 months ago by klee

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 tscrim

Thanks. Sounds good. Green bot => positive review.

comment:10 Changed 10 months ago by klee

  • Status changed from needs_review to positive_review

comment:11 Changed 10 months ago by vbraun

  • Branch changed from u/klee/32615 to 0a77fa52ca71ec76aca7ad9a7867b66828e6c761
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.