#10459: serious troubles with gcd
-----------------------------+----------------------------------------------
Reporter: dsm | Owner: was
Type: defect | Status: new
Priority: major | Milestone:
Component: number theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
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."
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10459>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
