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 pbruin)

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 pbruin

  • Description modified (diff)

comment:2 Changed 6 years ago by pbruin

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

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?

comment:4 Changed 6 years ago by pbruin

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 bruno

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

  • Branch changed from u/pbruin/18461-Field_gcd_univariate_polynomial to 908ace780e3545fec31175c6040520403e60fefd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.