Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#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:

Status badges

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)

trac_13014_try_QQ_lcm_v4.patch (7.0 KB) - added by D.S. McNeil 10 years ago.
try QQ *after* trying ZZ, now with more lcm

Download all attachments as: .zip

Change History (25)

comment:1 Changed 10 years ago by D.S. McNeil

Priority: majorminor

comment:2 Changed 10 years ago by D.S. McNeil

Status: newneeds_review

comment:3 Changed 10 years ago by Dan Drake

Authors: Douglas McNeil
Reviewers: Dan Drake

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. :)

comment:4 Changed 10 years ago by D.S. McNeil

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:5 Changed 10 years ago by Dan Drake

Status: needs_reviewpositive_review

Looks good.

comment:6 Changed 10 years ago by Dan Drake

Status: positive_reviewneeds_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 D.S. McNeil

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.

Last edited 10 years ago by D.S. McNeil (previous) (diff)

comment:8 Changed 10 years ago by D.S. McNeil

Status: needs_workneeds_review

comment:9 Changed 10 years ago by William Stein

Reviewers: Dan DrakeDan Drake, William Stein
Status: needs_reviewneeds_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 Changed 10 years ago by D.S. McNeil

(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 in reply to:  10 Changed 10 years ago by William Stein

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 D.S. McNeil

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 D.S. McNeil

*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 D.S. McNeil

Status: needs_workneeds_review

comment:15 Changed 10 years ago by William Stein

Status: needs_reviewpositive_review

looks great to me!

comment:16 Changed 10 years ago by D.S. McNeil

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 D.S. McNeil

try QQ *after* trying ZZ, now with more lcm

comment:17 Changed 10 years ago by Jeroen Demeyer

Component: basic arithmeticsymbolics

comment:18 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-5.1sage-5.2
Type: PLEASE CHANGEenhancement

comment:19 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.2.beta0
Resolution: fixed
Status: positive_reviewclosed

comment:20 Changed 10 years ago by Jeroen Demeyer

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 D.S. McNeil

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 Jeroen Demeyer

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 D.S. McNeil

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.

comment:24 Changed 10 years ago by Jeroen Demeyer

OK, see #13926.

Note: See TracTickets for help on using tickets.