Slow gcd for sparse polynomials

[katestange]

The following code produces a couple small sparse polynomials and times the gcd function:

R.<Z> = PolynomialRing(ZZ, sparse=True)
g = R(0)
f = R(0)
for i in range(10):
    g += Z^randint(1,10^5)
    f += Z^randint(1,10^5)
timeit("gcd(f,g)")

The results are disappointing:

5 loops, best of 3: 880 ms per loop

However, if we remove the "sparse=True" tag, the results are much better:

5 loops, best of 3: 46.6 ms per loop

This is highly repeatable, on my laptop and on the single cell server, on both larger and smaller examples. I don't see any essential reason this ought to be true, so I'm calling it a defect, but perhaps the community knows more about the efficiency issues of sparse polynomials...

CC: @katestange

Component: basic arithmetic

Keywords: gcd, polynomials, sparse

Author: katestange

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