#10459 closed defect (duplicate)
serious troubles with gcd
Reported by: | dsm | Owned by: | was |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | number theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | Luis Felipe Tabera Alonso, Douglas McNeil | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Current 4.6 release. This is very, very, very dangerous:
sage: a, b, c (2, 2, 2) sage: a == b, a==c (True, True) sage: gcd(a,b) 2 sage: gcd(a,c) 1
This occurs because at some point during the calculation, one of these things -- by virtue of being divided by 1 (!) -- became not like the others:
sage: map(type, [a,b,c]) [<type 'sage.rings.integer.Integer'>, <type 'sage.rings.integer.Integer'>, <type 'sage.rings.rational.Rational'>]
and for reasons I can't understand, rational.pyx chooses to return 1 as the gcd, when far more sensible alternatives are available. Moreover, a reasonable (naturally arbitrary, but reasonable) definition of lcm for rationals which reduces to the expected integer values is already implemented, and we can define a sane gcd via a*b = gcd(a,b) * lcm(a,b):
sage: lcm(4/3,1/3) 4/3 sage: lcm(4/1,6/1) 12 sage: sane_gcd = lambda a,b: a*b/lcm(a,b) sage: sane_gcd(4/3, 1/3) 1/3 sage: sane_gcd(4/3, 1/3) * lcm(4/3, 1/3) 4/9 sage: sane_gcd(4/1, 6/1) 2 sage: sane_gcd(4/1, 6/1) * lcm(4/1, 6/1) 24
which seems to be how pari does it, although I only checked a few values.
gcd/lcm have a bit of a history: see trac 3214, and more directly on point 8111. From reading the posted code in 3214, it looks like at one point (~3.3) it may behaved the way I think it should.
There are only two things I can think of to do:
(1) Use the preexisting lcm for rationals to define a gcd for rationals, which nicely gives integer-compatible results. This is my preferred option.
(2) Fail very loudly when computing either the lcm or the gcd of a rational number, so that users know they have to wrap arguments in Integer to get sensible results (i.e. the right answers when the arguments are right and error messages when not).
The current behaviour is all kinds of broken, and now I'm worried about everything I've ever done computing integer sequences in Sage. One single division in anything with a gcd call means everything after is probably wrong.
If it were a bug, that'd be unfortunate enough, but according to the docstring it was a deliberate decision to do it this way: "[..] but for simplicity we choose to always return 1."
Change History (8)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
Oops! I am sorry that I opened a new ticket for the same issue: #10771. It has a patch, is ready for review, and for fraction fields of a UFD (including QQ) it has the property gcd(x,y)*lcm(x,y)==x*y
up to a unit in the base ring (not just up to a unit in the fraction field).
Should the ticket here better be marked as a duplicate, although it came first?
comment:3 Changed 10 years ago by
Makes sense to me.
comment:4 Changed 9 years ago by
- Milestone set to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
The current behavior is the expected one. This ticket should be closed as a duplicate to #10771.
Douglas, do you agree with that?
comment:5 Changed 9 years ago by
Yep, Simon's work fixed it. I think there's a minor extension I have a patch for around but I'll open a separate ticket for that later, so this one can be closed as a duplicate.
comment:6 Changed 9 years ago by
- Reviewers set to Luis Felipe Tabera Alonso, Douglas McNeily
- Status changed from needs_review to positive_review
comment:7 Changed 9 years ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
comment:8 Changed 9 years ago by
- Reviewers changed from Luis Felipe Tabera Alonso, Douglas McNeily to Luis Felipe Tabera Alonso, Douglas McNeil
For a related tichet, check #9819 where it is discussed to add a generic gcd or lcm method to fields.