Opened 2 years ago

Closed 2 years ago

Last modified 23 months ago

#26433 closed defect (fixed)

Slowness in generic quo_rem

Reported by: caruso Owned by:
Priority: major Milestone: sage-8.5
Component: commutative algebra Keywords:
Cc: Merged in:
Authors: Xavier Caruso, Travis Scrimshaw Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 7047040 (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by tscrim)

While working on #26405, I noticed that the generic implementation of quo_rem is very slow. Indeed, compare:

sage: R.<a> = Zq(2^3)
sage: S.<x> = R[]
sage: P = S.random_element(degree=100)
sage: t = R.random_element()

sage: %timeit _ = P(t)
10000 loops, best of 3: 145 µs per loop

sage: Q = x - t
sage: %timeit _ = P % Q
1000 loops, best of 3: 1.06 ms per loop

Change History (14)

comment:1 Changed 2 years ago by caruso

  • Description modified (diff)

comment:2 Changed 2 years ago by caruso

  • Branch set to u/caruso/slowness_in_generic_quo_rem

comment:3 Changed 2 years ago by git

  • Commit set to cb8db697a1b1bd8d9aaeb20774c581641fb56e97

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

cb8db69Faster implementation of generic quo_rem

comment:4 Changed 2 years ago by caruso

Timings are now:

sage: %timeit _ = P % Q
1000 loops, best of 3: 210 µs per loop

comment:5 Changed 2 years ago by caruso

  • Status changed from new to needs_review

comment:6 Changed 2 years ago by git

  • Commit changed from cb8db697a1b1bd8d9aaeb20774c581641fb56e97 to ce544ccf681b94ca149803ca5d5ca5f0d3c3ce2c

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

ce544ccTypo

comment:7 Changed 2 years ago by tscrim

  • Branch changed from u/caruso/slowness_in_generic_quo_rem to u/tscrim/slowness_generic_quo_rem-26433
  • Commit changed from ce544ccf681b94ca149803ca5d5ca5f0d3c3ce2c to 1ca2c054271ae4dfa6719efe6bae1fc6bcc331fe
  • Description modified (diff)
  • Reviewers set to Travis Scrimshaw

I made a few Cython improvements. I also pulled out the if statement because I felt the code duplication was minimal and it would be better to avoid doing the if check every time in the loop.

If my changes are good, then positive review (with the author name is filled in).


New commits:

7603245Initial implementation.
592aa5bFixed doctests from recent versions.
177e074trac #15485 fixing the catalog
2febb38Improving documentation, changing FusionAlgebra -> VerlindeAlgebra, other updates.
4492c9dFixing various small things.
80b858aMerge branch 'u/caruso/slowness_in_generic_quo_rem' of git://trac.sagemath.org/sage into u/tscrim/slowness_generic_quo_rem-26433
1ca2c05Some small other improvements.
Version 0, edited 2 years ago by tscrim (next)

comment:8 Changed 2 years ago by git

  • Commit changed from 1ca2c054271ae4dfa6719efe6bae1fc6bcc331fe to 7047040f0fb3294c955241d3751f6b168ea020ef

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

7047040Some small other improvements.

comment:9 Changed 2 years ago by caruso

  • Authors set to Xavier Caruso, Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:10 Changed 2 years ago by caruso

The patchbot reports one failing doctest in src/sage/geometry/polyhedron/library.py but I guess it is not related to this ticket (and the test passes on my computer).

comment:11 Changed 2 years ago by vbraun

  • Branch changed from u/tscrim/slowness_generic_quo_rem-26433 to 7047040f0fb3294c955241d3751f6b168ea020ef
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:12 Changed 2 years ago by embray

  • Milestone changed from sage-8.4 to sage-8.5

This should be re-targeted for 8.5.

comment:13 Changed 23 months ago by mmezzarobba

  • Commit 7047040f0fb3294c955241d3751f6b168ea020ef deleted

A regression that may be due to this change: #26433.

comment:14 Changed 23 months ago by tscrim

See #26907.

Note: See TracTickets for help on using tickets.