Stability for gcd(x,x)

[saraedum]

Currently, trivial gcds do not return the exact element from the input:

sage: R.<x> = QQ[]
sage: gcd(x,x) is x
False

This is unfortunate because such trivial gcds get computed frequently, and any cached properties on the returned gcd are lost.

CC: @tscrim

Component: commutative algebra

Keywords: sd86.5, sd87, padicIMA

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

[roed314]

Changed keywords from sd86.5 to sd86.5, sd87

[roed314]

Changed keywords from sd86.5, sd87 to sd86.5, sd87, padicIMA

[365a0c67-81c0-4123-b354-fa6cea4e9402]

comment:3

Should we change all implementations of gcd (to make a special exception for the trivial gcd), or are there specific ones in mind?

[saraedum]

comment:5

varul: I personally only care about (univariate) polynomial rings. At least in exact rings, I can imagine that if the current implementation has gcd(x,x) == x, then gcd(x,x) is x could be true.

[saraedum]

comment:6

For the inexact ones, we could say that gcd(x,x) is x should be true if gcd(x,x)._cache_key() == x._cache_key().

[nbruin]

comment:7

How far do you want to take this?

sage: GCD(3*x,3*x)
x

It looks to me like GCD(f,f) should normally NOT be identical to f. If you want to put an optimization into sage for code that calls GCD(x,x) very frequently then you can do that (provided you can do that at essentially zero penalty for the general case), but this should not be part of the API.

In practice, it means your code should probably not depend on the optimization being present, because I'd expect that a rewrite down the road would make it disappear again. If you are finding you need this optimization, you're probably better off writing

(x is y) select x else gcd(x,y)

in the relevant places. }}}

[saraedum]

comment:8

My code does not call the gcd. It's called indirectly in a couple of places. I forget the details but I could create some stack traces to find how this goes exactly. My code won't depend on the optimization being present but it's performance is going to be better if the optimization is present.

I don't want to add this requirement to the API of gcd. However, I would of course add a doctest to polynomial gcds linking back to this ticket and checking that some cached value does not disappear maybe.