lcm for SR rationals

[dsm]

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.

[ddrake]

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

[dsm]

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

[ddrake]

Looks good.

[ddrake]

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.

[dsm]

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.

[was]

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

[dsm]

(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?

[was]

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.

[dsm]

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.

[dsm]

*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.

[was]

looks great to me!

[dsm]

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.

[dsm]

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

[jdemeyer]

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

[dsm]

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

[jdemeyer]

It's clear that this either needs to fixed or that this patch will need to be reverted.

[dsm]

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.

[jdemeyer]

OK, see #13926.