#26433 closed defect (fixed)
Slowness in generic quo_rem
Reported by:  caruso  Owned by:  

Priority:  major  Milestone:  sage8.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 )
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:2 Changed 2 years ago by
 Branch set to u/caruso/slowness_in_generic_quo_rem
comment:3 Changed 2 years ago by
 Commit set to cb8db697a1b1bd8d9aaeb20774c581641fb56e97
Branch pushed to git repo; I updated commit sha1. New commits:
cb8db69  Faster implementation of generic quo_rem

comment:4 Changed 2 years ago by
Timings are now:
sage: %timeit _ = P % Q 1000 loops, best of 3: 210 µs per loop
comment:5 Changed 2 years ago by
 Status changed from new to needs_review
comment:6 Changed 2 years ago by
 Commit changed from cb8db697a1b1bd8d9aaeb20774c581641fb56e97 to ce544ccf681b94ca149803ca5d5ca5f0d3c3ce2c
Branch pushed to git repo; I updated commit sha1. New commits:
ce544cc  Typo

comment:7 Changed 2 years ago by
 Branch changed from u/caruso/slowness_in_generic_quo_rem to u/tscrim/slowness_generic_quo_rem26433
 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).
comment:8 Changed 2 years ago by
 Commit changed from 1ca2c054271ae4dfa6719efe6bae1fc6bcc331fe to 7047040f0fb3294c955241d3751f6b168ea020ef
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7047040  Some small other improvements.

comment:10 Changed 2 years ago by
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
 Branch changed from u/tscrim/slowness_generic_quo_rem26433 to 7047040f0fb3294c955241d3751f6b168ea020ef
 Resolution set to fixed
 Status changed from positive_review to closed
comment:12 Changed 2 years ago by
 Milestone changed from sage8.4 to sage8.5
This should be retargeted for 8.5.
comment:13 Changed 2 years ago by
 Commit 7047040f0fb3294c955241d3751f6b168ea020ef deleted
A regression that may be due to this change: #26433.
comment:14 Changed 2 years ago by
See #26907.