#13014 closed enhancement (fixed)
lcm for SR rationals
Reported by: | D.S. McNeil | Owned by: | Alex Ghitza |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.2 |
Component: | symbolics | Keywords: | sd40.5 |
Cc: | Merged in: | sage-5.2.beta0 | |
Authors: | Douglas McNeil | Reviewers: | Dan Drake, William Stein |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
At the moment, we can do
sage: gcd(2/3, 4/5) 2/15 sage: lcm(2/3, 4/5) 4 sage: gcd(2/3, 4/5) * lcm(2/3, 4/5) == 2/3*4/5 True
but
sage: gcd(SR(2/3), SR(4/5)) 2/15 sage: lcm(SR(2/3), SR(4/5)) --------------------------------------------------------------------------- TypeError Traceback (most recent call last) /Users/mcneil/sagedev/sage-5.1.beta0/devel/sage-hack/sage/plot/<ipython console> in <module>() /Users/mcneil/sagedev/sage-5.1.beta0/local/lib/python2.7/site-packages/sage/rings/arith.pyc in lcm(a, b) 1646 return ZZ(a).lcm(ZZ(b)) 1647 except TypeError: -> 1648 raise TypeError, "unable to find lcm of %s and %s"%(a,b) 1649 return LCM(b) 1650 TypeError: unable to find lcm of 2/3 and 4/5
We can improve the symmetry just by trying QQ instead of ZZ, as discussed in the comments to #10771.
Attachments (1)
Change History (25)
comment:1 Changed 10 years ago by
Priority: | major → minor |
---|
comment:2 Changed 10 years ago by
Status: | new → needs_review |
---|
comment:3 Changed 10 years ago by
Authors: | → Douglas McNeil |
---|---|
Reviewers: | → Dan Drake |
comment:4 Changed 10 years ago by
Not sure how that happened. :) Not a SyntaxError? because ZZ is perfectly valid as a name and the hashes just indicate a comment. Many's the time I've caused a bug because I've forgotten that simply naming something doesn't execute it..
comment:6 Changed 10 years ago by
Status: | positive_review → needs_work |
---|
Oops. This causes a couple minor doctest failures in symbolic/expression.pyx
:
sage -t --long -force_lib "devel/sage/sage/symbolic/expression.pyx" #0: simplify_sum(expr='sum(q^k,k,0,inf)) #1: simplify_sum(expr=a*'sum(q^k,k,0,inf)) ********************************************************************** File "/home/drake/s/sage-5.1.beta0/devel/sage/sage/symbolic/expression.pyx", line 2611: sage: (Mod(2,7)*x^2 + Mod(2,7))^7 Expected: 128*(x^2 + 1)^7 Got: (2*x^2 + 2)^7 ********************************************************************** File "/home/drake/s/sage-5.1.beta0/devel/sage/sage/symbolic/expression.pyx", line 2618: sage: gcd(t,t).parent() Expected: Integer Ring Got: Rational Field **********************************************************************
I'll look into these.
comment:7 Changed 10 years ago by
Okay, here's what's going on. I'd be fine with simply changing the second doctest but the first one is actually a change in behaviour and so we should salvage it. Before this patch, we had
sage: gcd(2 % 7, 2 % 7) 2 sage: parent(_) Integer Ring
i.e. we move out of Zmod(7) even though we don't need to. See, e.g., the following sage-support thread (https://groups.google.com/forum/#!topic/sage-support/_LvmAECVeDg/discussion) for related issues.
I think the simplest thing to do to get QQ working without changing the original doctests would be to try ZZ first and if that succeeds don't try QQ. (At the moment we leap right to QQ.) After we fix the gcds in Zmod(n), the first doctest will need to change. I'll submit a new patch.
comment:8 Changed 10 years ago by
Status: | needs_work → needs_review |
---|
comment:9 Changed 10 years ago by
Reviewers: | Dan Drake → Dan Drake, William Stein |
---|---|
Status: | needs_review → needs_work |
REFEREE REPORT:
Sorry, but I have a few issues...
- Doing this is a sort of gotcha mistake in Python:
raise TypeError("unable to find gcd of %s and %s"%(a,b))
The problem is that the error message may take a very, very long time to generate. The error should just be TypeError("unable to compute gcd")
. Similar remarks for lcm.
- Give me an example in the docstring that illustrates every exception in your code actually getting raised. If you can't, then maybe the code isn't needed.
- The bool in all your tests is not needed since nothing is symbolic in the comparison. E.g.,
sage: bool(gcd(2/5, 3/7) == gcd(SR(2/5), SR(3/7)))
should be
sage: gcd(2/5, 3/7) == gcd(SR(2/5), SR(3/7))
comment:10 follow-up: 11 Changed 10 years ago by
(1) Sure, I can change those. Those were pre-existing.
(2) Will do-- you might be right it can't actually be tripped, because
a,b = cm.canonical_coercion(a,b)
might already fail. I thought I had a case where it did; will see if I can find it.
(3) I don't agree with your last comment. Even before this patch, we have parent(gcd(SR(3), SR(6)) == SR, and so the bool is necessary. Do you think the current behaviour should change and gcd(SR(3), SR(6)) should return something not in SR?
comment:11 Changed 10 years ago by
Replying to dsm:
(3) I don't agree with your last comment. Even before this patch, we have parent(gcd(SR(3), SR(6)) == SR, and so the bool is necessary. Do you think the current behaviour should change and gcd(SR(3), SR(6)) should return something not in SR?
Sorry, I was actually testing your code with lcm, and there the parent is not SR:
sage: parent(lcm(SR(2/5), SR(3/7))) Rational Field
I thought your gcd would be the same. It's bad that it isn't. I think the answer should be in SR as you say, though. So replace 3 by the error regarding the parent for lcm.
comment:12 Changed 10 years ago by
Ah. That's due to the quirk that we have a .gcd defined in expression.pyx and not an .lcm, and so slightly different paths are taken. Should be able to fix that without too much work.
comment:13 Changed 10 years ago by
*whew* Well, that was fun.
Expressions now have an .lcm method (defined as self * b / self.gcd(b)), with associated tests to make sure that the corner cases I could think of work, mostly involving zeroes. The error messages are now less informative (but less likely to crash if they accidentally receive some object with a really long str), which necessitated changes elsewhere where the old error message was being doctested. That the error messages are actually produced is tested locally as well.
lcm and gcd of symbolic objects now stay in SR.
We still need to fix gcd taking objects out of Zmod(n) but that can wait for another ticket.
comment:14 Changed 10 years ago by
Status: | needs_work → needs_review |
---|
comment:16 Changed 10 years ago by
Morning delta, typo in the tests:
< + Verify that objects without gcd methods but which can't be --- > + Verify that objects without lcm methods but which can't be
Changed v4 in place.
Changed 10 years ago by
Attachment: | trac_13014_try_QQ_lcm_v4.patch added |
---|
try QQ *after* trying ZZ, now with more lcm
comment:17 Changed 10 years ago by
Component: | basic arithmetic → symbolics |
---|
comment:18 Changed 10 years ago by
Milestone: | sage-5.1 → sage-5.2 |
---|---|
Type: | PLEASE CHANGE → enhancement |
comment:19 Changed 10 years ago by
Merged in: | → sage-5.2.beta0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:20 Changed 10 years ago by
This caused a massive slowdown for the command
sage: time p = polar_plot(lambda t: (100/(100+(t-pi/2)^8))*(2-sin(7*t)-cos(30*t)/2), -pi/4, 3*pi/2, color="red", plot_points=1000)
from 9 to 23 seconds. See https://groups.google.com/forum/?fromgroups#!topic/sage-devel/EzFPIG6EFMI
comment:21 Changed 10 years ago by
Urf, that's no good at all. I'll have a look tonight if no one else gets to it. Since this wasn't supported before, then maybe (1) some code was implicitly expecting a TypeError
and now isn't getting one, or (2) something still gets a TypeError
but the expense of trying to convert it to QQ as well as ZZ is too high. :-/
comment:22 Changed 10 years ago by
It's clear that this either needs to fixed or that this patch will need to be reverted.
comment:23 Changed 10 years ago by
I think it should probably come out entirely. What seems to be going on is that gcd is getting called during evaluation on a lot of floats, e.g.
sage: f = lambda t: 1/(t+pi) sage: f(1.5r) GCDing 1 <type 'int'> 1 0 <type 'int'> 0 returning on ZZ 1 GCDing 1.5 <type 'float'> 1.5 1.0 <type 'float'> 1.0 returning on QQ 1/2 GCDing 3.0 <type 'float'> 3.0 2.0 <type 'float'> 2.0 returning on ZZ 1
Previously, only integers would be tried, and they would typically (though not always!) fail. Floats, however, can be coerced to QQ.. and so they are. Sage is implicitly relying on the fact that gcd will fail, and fail quickly, for floats. I can recover the original runtimes by adding more explicit typechecks but that isn't very robust.
Far and away the simplest thing is to revert it, more's the pity. On the bright side I probably exercise this code more than anyone else and even I don't use it very much.
Positive review, but line 35 of your patch has a weird "ZZ" at the beginning of the line. I'm actually a bit surprised it's not a syntax error.
Take that out of your patch and change this to positive review. :)