Opened 6 years ago
Closed 6 years ago
#18461 closed enhancement (fixed)
Implement Field._gcd_univariate_polynomial()
Reported by: | pbruin | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.8 |
Component: | basic arithmetic | Keywords: | polynomial gcd |
Cc: | saraedum | Merged in: | |
Authors: | Peter Bruin | Reviewers: | Bruno Grenet |
Report Upstream: | N/A | Work issues: | |
Branch: | 908ace7 (Commits) | Commit: | 908ace780e3545fec31175c6040520403e60fefd |
Dependencies: | Stopgaps: |
Description (last modified by )
The goal of this ticket is to implement a Cython method Field._gcd_univariate_polynomial()
using the standard Euclidean algorithm. This is much faster than Fields.ParentMethods._gcd_univariate_polynomial()
, which calls EuclideanDomains.ElementMethods.gcd()
, since both are Python methods. (The _gcd_univariate_polynomial
mechanism was introduced in #13442.)
The following bug can then be fixed by just removing PolynomialRealDense.gcd()
, which does not take into account the case where one of the arguments of gcd
is zero:
sage: R.<x> = RR[] sage: x.gcd(R.zero()) Traceback (most recent call last): ... TypeError: 'MinusInfinity' object cannot be interpreted as an index
Removing this method without implementing Field._gcd_univariate_polynomial()
(falling back on Python code) is about twice as slow; with this ticket there is no slowdown.
Similarly, to make CC
and QQbar
use the new method instead of Python code, we also remove the now obsolete Polynomial_generic_field.gcd()
.
Change History (6)
comment:1 Changed 6 years ago by
- Description modified (diff)
comment:2 Changed 6 years ago by
- Branch set to u/pbruin/18461-Field_gcd_univariate_polynomial
- Commit set to 908ace780e3545fec31175c6040520403e60fefd
- Status changed from new to needs_review
comment:3 Changed 6 years ago by
comment:4 Changed 6 years ago by
I just tested again with the following setup:
R.<x> = RR[] z = R.zero() f = x^2 + 3 g = x^3 + 5
With this branch (i.e. with Field._gcd_univariate_polynomial
):
sage: %timeit z.gcd(z) The slowest run took 37.08 times longer than the fastest. This could mean that an intermediate result is being cached 1000000 loops, best of 3: 1.77 µs per loop sage: %timeit x.gcd(z) The slowest run took 22.57 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 4.34 µs per loop sage: %timeit z.gcd(x) The slowest run took 66.36 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 10.5 µs per loop sage: %timeit x.gcd(x) The slowest run took 13.64 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 11.1 µs per loop sage: %timeit f.gcd(g) The slowest run took 24.83 times longer than the fastest. This could mean that an intermediate result is being cached 10000 loops, best of 3: 33.6 µs per loop
With this branch after removing Field._gcd_univariate_polynomial
:
sage: %timeit z.gcd(z) The slowest run took 16.42 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 6.81 µs per loop sage: %timeit x.gcd(z) The slowest run took 92.70 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 11.4 µs per loop sage: %timeit z.gcd(x) The slowest run took 15.38 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 19.2 µs per loop sage: %timeit x.gcd(x) The slowest run took 4.43 times longer than the fastest. This could mean that an intermediate result is being cached 10000 loops, best of 3: 19.9 µs per loop sage: %timeit f.gcd(g) The slowest run took 4.04 times longer than the fastest. This could mean that an intermediate result is being cached 10000 loops, best of 3: 42.7 µs per loop
I don't have an explanation for the discrepancy between the slowest and fastest runs; as far as I know there is no caching.
For complicated polynomials, the difference is undoubtedly smaller because most time is spent in quo_rem
, which is not touched by this branch.
comment:5 Changed 6 years ago by
- Reviewers set to Bruno Grenet
- Status changed from needs_review to positive_review
Ok, I reproduced the same slowdown if Field._gcd_univariate_polynomial
is removed. Passes all tests, fine for me!
comment:6 Changed 6 years ago by
- Branch changed from u/pbruin/18461-Field_gcd_univariate_polynomial to 908ace780e3545fec31175c6040520403e60fefd
- Resolution set to fixed
- Status changed from positive_review to closed
This looks good to me. Yet, I have not been able to reproduce the slowdown you mention without the new method: May you give some details?