Implement Field._gcd_univariate_polynomial()

[pjbruin]

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().

CC: @saraedum

Component: basic arithmetic

Keywords: polynomial gcd

Author: Peter Bruin

Branch/Commit: 908ace7

Reviewer: Bruno Grenet

Issue created by migration from https://trac.sagemath.org/ticket/18461

[pjbruin]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-We implement `Field._gcd_univariate_polynomial()` using the standard Euclidean algorithm.  This is much faster than the existing Python method `Fields.ParentMethods._gcd_univariate_polynomial()` (which calls `EuclideanDomains.ElementMethods.gcd()`).  (The `_gcd_univariate_polynomial` mechanism was introduced in #13442.)
+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:
 
@@ -10,3 +10,5 @@
 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()`.

[pjbruin]

Branch: u/pbruin/18461-Field_gcd_univariate_polynomial

[pjbruin]

Commit: 908ace7

[bgrenet]

comment:3

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?

[pjbruin]

comment:4

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.

[bgrenet]

Reviewer: Bruno Grenet

[bgrenet]

comment:5

Ok, I reproduced the same slowdown if Field._gcd_univariate_polynomial is removed. Passes all tests, fine for me!

[vbraun]

Changed branch from u/pbruin/18461-Field_gcd_univariate_polynomial to 908ace7