Opened 9 years ago

Closed 8 years ago

Last modified 8 years ago

#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 9 years ago by lftabera

For a related tichet, check #9819 where it is discussed to add a generic gcd or lcm method to fields.

comment:2 Changed 9 years ago by SimonKing

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 9 years ago by dsm

Makes sense to me.

comment:4 Changed 8 years ago by lftabera

  • 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 8 years ago by dsm

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 8 years ago by kcrisman

  • Reviewers set to Luis Felipe Tabera Alonso, Douglas McNeily
  • Status changed from needs_review to positive_review

comment:7 Changed 8 years ago by jdemeyer

  • Resolution set to duplicate
  • Status changed from positive_review to closed

comment:8 Changed 8 years ago by jdemeyer

  • Reviewers changed from Luis Felipe Tabera Alonso, Douglas McNeily to Luis Felipe Tabera Alonso, Douglas McNeil
Note: See TracTickets for help on using tickets.