implement gcd(a,b,hold=True)

rwst commented 10 years ago

The implemented behaviour of gcd is consistent if its arguments are rational numbers or polynomials. Trying to give a symbolic variable will convert to polynomial which behaves unexpectedly:

sage: x=var('x')
sage: gcd(x,4)
1

The natural way to handle it is using the keyword hold:

sage: gcd(x,4,hold=True)
---------------------------------------------------------------------------
Traceback (most recent call last)
...
TypeError: gcd() takes no keyword arguments

As comment:18 shows this may not be easy and involve other changes.

See also #15497

CC: @sagetrac-kbaut

Component: symbolics

Stopgaps: todo

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

kcrisman commented 10 years ago

comment:1

One could argue this is (currently) user error, but this would be a great enhancement.

6899de36-7e89-4488-afcf-d9c803bd61bc commented 10 years ago

comment:3

Here's another example, which seems to put this in the "mathematically wrong answer" category:

sage: sum(gcd(x, 4), x, 1, 4)
4

I would expect the answer to be 8 instead of 4:

sage: [gcd(x, 4) for x in range(1, 5)]
[1, 2, 1, 4]
sage: sum(gcd(x, 4) for x in range(1, 5))
8

6899de36-7e89-4488-afcf-d9c803bd61bc commented 10 years ago

Stopgaps: todo

kcrisman commented 10 years ago

comment:4

I think the problem is that while we do get the "right" thing when two polynomials are involved, we somehow don't for a polynomial and an integer, and this isn't well documented. I agree that the end user may not care and that we should find a way to fix it (or at least to raise an error when a symbolic thing shows up in it). This won't be completely trivial, though.

kcrisman commented 10 years ago

comment:5


        <type 'sage.rings.integer.Integer'>

    TESTS:

    The following shows that indeed coercion takes place before computing
    the gcd. This behaviour was introduced in trac ticket #10771::

        sage: R.<x>=QQ[]
        sage: S.<x>=ZZ[]
        sage: p = S.random_element()
        sage: q = R.random_element()
        sage: parent(gcd(1/p,q))
        Fraction Field of Univariate Polynomial Ring in x over Rational Field
        sage: parent(gcd([1/p,q]))
        Fraction Field of Univariate Polynomial Ring in x over Rational Field

and indeed

sage: parent(gcd(x,1))
Symbolic Ring

So in the symbolic ring this IS the gcd. Hmm. And if you think of this as a polynomial, it makes sense.

So I'm not sure what to say here. The 4 might be a red herring in this case, because we consider SR or whatever as more about polynomials over a field, so the gcd is automatically one - maybe? Also check out x.gcd??. Just raising questions about what the "right" thing to do is.


    Make sure we try QQ and not merely ZZ (:trac:`13014`)::

        sage: bool(gcd(2/5, 3/7) == gcd(SR(2/5), SR(3/7)))
        True

rwst commented 10 years ago

Description changed:

--- 
+++ 
@@ -6,3 +6,5 @@
 1

See also #15497 + +Also an enhancement in order to be able to use gcd() in returned expression results.

rwst commented 10 years ago

Description changed:

--- 
+++ 
@@ -4,7 +4,10 @@
 sage: x=var('x')
 sage: gcd(x,4)
 1
+sage: gcd(x,4,hold=True)
+---------------------------------------------------------------------------
+Traceback (most recent call last)
+...
+TypeError: gcd() takes no keyword arguments

See also #15497

-Also an enhancement in order to be able to use gcd() in returned expression results.

rwst commented 10 years ago

comment:7

Replying to @kcrisman:

I agree that all examples you give are consistent *if the gcd is considered not as a symbolic function. It may simply need an implementation of hold=True to allow that usage. The only problem then that I see is that people would have to learn the distinction between an operation and a symbolic function, which they have to in many places anyway.

So just make sure a big NOTE is given in the documentation.

6899de36-7e89-4488-afcf-d9c803bd61bc commented 10 years ago

comment:8

Are there any problematic cases that don't involve the sum function?

I'm wondering if the implementation of sum is actually the issue. sum(expression, v, a, b) evaluates the expression before substituting values for the variable, unlike sum(expression for v in range(a, b+1)). Should they be equivalent?

nbruin commented 10 years ago

comment:9

Replying to @sagetrac-kbaut:

I'm wondering if the implementation of sum is actually the issue. sum(expression, v, a, b) evaluates the expression before substituting values for the variable, unlike sum(expression for v in range(a, b+1)). Should they be equivalent?

That they are different is a rather fundamental python language feature. Making the two behave equivalently would require rather major surgery on the python parser or some nasty trickery in preparsing.

rwst commented 10 years ago

comment:10

Replying to @sagetrac-kbaut:

Are there any problematic cases that don't involve the sum function?

sage: f(x)=gcd(x,4)/gcd(x,8)
sage: [f(x) for x in range(10)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

nbruin commented 10 years ago

comment:11

You'd first need to decide what "gcd(A,B)" of two symbolic expressions is:

if it's "integer" gcd then it can be evaluated for integers entries, it's an error if you feed it something else ostensibly numeric, and it can be left unevaluated if there are variables in there.
if it's (univariate) polynomial gcd, there needs to be some heuristic to choose the variable wrt. which it would be the gcd (or better, this variable would be part of the input). Anything else would be considered an (invertible) coefficient. This would never be left unevaluated. This is close to what we have now.

We have too little information to define gcd on SR properly. Currently even this doesn't work:

gcd(x,sqrt(2)*x)

The gcd we are currently interfacing with is:

x.gcd

which is limited to polynomials over QQ, but at least it fixes the choice: it's polynomial gcd. That means gcd(x,4) should indeed be 1 (or at least a constant).

In any setting, gcd tends to be not stable under evaluation, meaning that if

G(x) = gcd (a(x),b(x))

then for a specialization x0 of x, one can easily have that gcd(a(x0),b(x0)) != G(x0). That means a "symbolic" gcd will always be problematic.

rwst commented 10 years ago

comment:12

That may be, but it presupposes that evaluation is demanded in SR. It does not touch my simple wish to hold off evaluation for some time, after which I will gladly use the evaluation already implemented.

So, what arguments against hold=True?

nbruin commented 10 years ago

comment:14

Replying to @rwst:

So, what arguments against hold=True?

How do you control when hold=True is triggered to be expanded? In particular, in

sum( gcd( x^2+n,x,hold=True),n,-2,2,hold=True )

what do you do to clear to "unhold" the expression and how do you control the order in which that happens? In particular, for your application, you'd need the values of n to be substituted before the hold on gcd is cleared.

rwst commented 10 years ago

comment:15

I see. But then the only reasonable way to achieve it is with different gcd functions, so one can sort out when to hold, i.e., the rational constant version would do it when an expression appeared as argument.

rwst commented 10 years ago

comment:16

There are more than one solution to represent the function gcd(a,n), a in QQ, n in ZZ. It is always a C-Finite sequence, so reviewing #15714 would help too.

rwst commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,13 +1,20 @@
-Defect because of
+The implemented behaviour of `gcd` is consistent if its arguments are rational numbers or polynomials. Trying to give a symbolic variable will
+convert to polynomial which behaves unexpectedly:

sage: x=var('x') sage: gcd(x,4) 1 + +The natural way to handle it is using the keyword `hold`: + + sage: gcd(x,4,hold=True)

Traceback (most recent call last) ... TypeError: gcd() takes no keyword arguments

+As [comment:18](#comment%3A18) shows this may not be easy and involve other changes.
+
 See also #15497

rwst commented 10 years ago

comment:18

Replying to @nbruin:

How do you control when hold=True is triggered to be expanded? In particular, in
sum( gcd( x^2+n,x,hold=True),n,-2,2,hold=True )
what do you do to clear to "unhold" the expression and how do you control the order in which that happens? In particular, for your application, you'd need the values of n to be substituted before the hold on gcd is cleared.

I do not understand. In what way is this different from

sum(sin(n*pi,hold=True),n,1,5,hold=True)
...
TypeError: symbolic_sum() got an unexpected keyword argument 'hold'

which simply does not work, and from which one usually comes to this:

sage: sum(sin(n*pi,hold=True) for n in range(1,6))
sin(pi) + sin(5*pi) + sin(4*pi) + sin(3*pi) + sin(2*pi)

nbruin commented 10 years ago

comment:19

Replying to @rwst:

I do not understand. In what way is this different from
sum(sin(n*pi,hold=True),n,1,5,hold=True)
...
TypeError: symbolic_sum() got an unexpected keyword argument 'hold'
which simply does not work, and from which one usually comes to this:
sage: sum(sin(n*pi,hold=True) for n in range(1,6))
sin(pi) + sin(5*pi) + sin(4*pi) + sin(3*pi) + sin(2*pi)

The problem is that "hold" semantics aren't well-defined, so you'd better make sure that for "held" expressions, the answers aren't wildly different depending on when the "hold" is lifted. Never mind that "hold" isn't implemented for sums. You can usually get an implicit hold by doing something like

f(N)=sum(...,n,1,N)

and with that transform you see that your suggested iterator expression is NOT the same:

sage: var("t,T")
(t, T)
sage: sum(sin(t*pi,hold=True),t,1,T)
0

The hold apparently gets lifted by "sum" already (because our "hold" doesn't get translated to maxima, perhaps because a corresponding notion doesn't exist for sine there) and apparently, sum simplifies the expression under the assumption that t is an integer.

That's why I think "hold" is not an appropriate mechanism for a wildly non-continuous function such as "gcd". It's meant to be a manipulation on (polynomial) expressions, not a symbolic function. I don't think SR is equipped to handle operations like that "symbolically".

I know systems like maple and mathematica tend to not make a distinction between "operations" and "symbolic expressions", allowing deferred evaluation on pretty much anything, and in my experience predictability and debuggability of code suffers from it.

Nothing prevents you from defining function("completely_inert_gcd") and writing expressions with that. The problem arises when you start trying to use simplification/evaluation rules on this expression. Normally, you'd from the inside to the outside; for your sum example you'd need it from the outside to the inside. We can't really have both if we don't have a way to indicate which method to use where.

rwst commented 10 years ago

comment:20

So, summarily, gcd itself has nothing to enhance in this direction, and this ticket should not be stretched to implement something only marginally useful.

saraedum commented 8 years ago

comment:21

I believe that this should be "positive review". It was set to invalid 20 months ago and nobody complained so it can probably go away.

sagemath / sage

implement gcd(a,b,hold=True) #16721

See also #15497

sage: x=var('x') sage: gcd(x,4) 1 + +The natural way to handle it is using the keyword `hold`: + + sage: gcd(x,4,hold=True)