Opened 6 years ago
Closed 5 years ago
#16721 closed enhancement (fixed)
implement gcd(a,b,hold=True)
Reported by: | rws | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | symbolics | Keywords: | |
Cc: | kbaut | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: | todo |
Description (last modified by )
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
Change History (22)
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
- Cc kbaut added
comment:3 Changed 6 years ago by
- Stopgaps set to todo
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
comment:4 follow-up: ↓ 8 Changed 6 years ago by
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.
comment:5 follow-up: ↓ 7 Changed 6 years ago by
<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
comment:6 Changed 6 years ago by
- Description modified (diff)
comment:7 in reply to: ↑ 5 Changed 6 years ago by
- Description modified (diff)
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.
comment:8 in reply to: ↑ 4 ; follow-ups: ↓ 9 ↓ 10 Changed 6 years ago by
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?
comment:9 in reply to: ↑ 8 Changed 6 years ago by
Replying to 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, unlikesum(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.
comment:10 in reply to: ↑ 8 Changed 6 years ago by
Replying to 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]
comment:11 Changed 6 years ago by
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.
comment:12 follow-up: ↓ 14 Changed 6 years ago by
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
?
comment:13 Changed 6 years ago by
- Summary changed from symbolic gcd() to implement gcd(a,b,hold=True)
comment:14 in reply to: ↑ 12 ; follow-up: ↓ 18 Changed 6 years ago by
Replying to rws:
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.
comment:15 Changed 6 years ago by
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.
comment:16 Changed 6 years ago by
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.
comment:17 Changed 6 years ago by
- Description modified (diff)
- Type changed from defect to enhancement
comment:18 in reply to: ↑ 14 ; follow-up: ↓ 19 Changed 6 years ago by
Replying to nbruin:
How do you control when
hold=True
is triggered to be expanded? In particular, insum( 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 ongcd
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)
comment:19 in reply to: ↑ 18 Changed 6 years ago by
Replying to rws:
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.
comment:20 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
So, summarily, gcd
itself has nothing to enhance in this direction, and this ticket should not be stretched to implement something only marginally useful.
comment:21 Changed 5 years ago by
- Status changed from needs_review to positive_review
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.
comment:22 Changed 5 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
One could argue this is (currently) user error, but this would be a great enhancement.