Ticket #3214 (reopened defect)

Opened 8 months ago

Last modified 4 days ago

[with patch, needs review] gcd needs improved coercion

Reported by: novoselt Assigned to: somebody
Priority: blocker Milestone: sage-3.3
Component: basic arithmetic Keywords:
Cc: robertwb, craigcitro, cremona

Description

I got very confused by the first line since I used to use gcd for clearing denominators: 

sage: gcd((1, 2/3, 1/6, 1/6))
1
sage: gcd((2/3, 1/6, 1/6))
1/6
sage: gcd((2/3, 1, 1/6, 1/6))
Traceback (most recent call last):
...
TypeError: Argument 'other' has incorrect type (expected sage.rings.rational.Rational, got sage.rings.integer.Integer)
sage: gcd((2/3, 2/2, 1/6, 1/6))
1/6

I'd expect all calls above to return 1/6.

Attachments

trac_3214.patch (12.2 kB) - added by AlexGhitza on 01/04/2009 10:22:14 AM.

Change History

10/26/2008 11:12:07 PM changed by mabshoff

  • status changed from new to closed.
  • resolution set to fixed.
  • milestone changed from sage-3.2.1 to sage-3.2.

This works now: 

----------------------------------------------------------------------
| Sage Version 3.2.alpha1, Release Date: 2008-10-26                  |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------

sage: gcd((2/3, 1, 1/6, 1/6))
1/6

Cheers,

Michael

10/26/2008 11:19:01 PM changed by mabshoff

  • cc set to robertwb.
  • status changed from closed to reopened.
  • resolution deleted.

But the first case is still broken. This might not be coercion related, though.

Cheers,

Michael

11/30/2008 03:52:45 PM changed by mabshoff

  • cc changed from robertwb to robertwb, craigcitro, cremona.

This seems critical enough to elevate its priority. Also CC some people who might be able and willing to fix it :)

Cheers,

Michael

11/30/2008 03:52:53 PM changed by mabshoff

  • priority changed from minor to critical.

12/28/2008 05:06:46 AM changed by AlexGhitza

  • summary changed from gcd needs improved coersion to [with patch, needs review] gcd needs improved coercion.

It is indeed not coercion-related. The computation of the gcd is done in a loop, from which one exits as soon as a gcd of 1 is obtained (ignoring the rest of the elements). In the case of elements with denominators (such as rational numbers or rational functions) this gives rise to the wrong answers reported above.

The attached trivial patch fixes this so that correct answers are returned.

12/28/2008 07:35:25 AM changed by mabshoff

  • priority changed from critical to blocker.
  • milestone changed from sage-3.4 to sage-3.3.

Arg, this really ought to go into 3.3.

Thanks for tracking this down Alex,

Michael

12/28/2008 08:57:03 AM changed by cremona

Hmmm. It seems a real pity to just delete the quick exit line since in most circumstances as soon as you have a unit you can return 1. This will result in a lot of calls to vi.gcd(g) where vi is random and g==1, so those had better be caught efficiently in the member gcd() function. (Incidentally, there was a reason for putting vi.gcd(g) and not g.gcd(vi), which I now forget.)

It's another field-of-fractions thing; in the example we are not really treating the rationals as elements of QQ, but as scaled elements of ZZ, where x.div(y) means y/x in ZZ even though x,y may be in QQ. Testing for .is_unit() certainly would not be appropriate. I cannot see a better way than what the patch does, unless we give up the nice behaviour that the gcd of a set of rationals is defined to be a generator of the ZZ-module they span.

12/29/2008 11:59:36 AM changed by robertwb

  • summary changed from [with patch, needs review] gcd needs improved coercion to [with patch, needs work] gcd needs improved coercion.

I agree that the quick exit shouldn't be deleted. I would propose either constructing a sequence (so all elements live in the same domain to begin with) or having the exit verify that the parents are all the same type (much faster than calling gcd).

12/30/2008 01:25:37 AM changed by AlexGhitza

Robert, I'm not sure I understand your suggestion. The current code already constructs a sequence. The problem is that when the universe of that sequence is QQ, bailing out of the loop as soon as one gets 1 is wrong.

If QQ were the only obstruction this would be easy to fix, but the same will happen with other fraction fields (number fields, p-adics, rational functions, etc.)

I'm actually getting more and more convinced that I don't like this use of gcd for fraction fields anyway; but I'll take this to sage-devel and see what people think.

12/30/2008 01:39:39 AM changed by robertwb

  • summary changed from [with patch, needs work] gcd needs improved coercion to [with patch, needs review] gcd needs improved coercion.

You have a good point. I've never used this function for elements of a fraction field, so I'm not even sure what the intended behavior/use cases are.

Please post to sage-devel, hopefully it will shed some light on what should happen here.

01/04/2009 10:22:14 AM changed by AlexGhitza

  • attachment trac_3214.patch added.

01/04/2009 10:28:23 AM changed by AlexGhitza

OK, following the discussion at http://groups.google.com/group/sage-devel/browse_thread/thread/35abc577b5ba78e7/170c0da22b9a36b9#170c0da22b9a36b9 I am implementing a trivial gcd() method for rational numbers and renaming the current rational gcd() to content(). The (newly) attached patch also touches a few other files in the sage library that are affected by this.

There is one doctest failure that I don't know how to deal with, in the symbolic gcd of ginac; sage -t symbolic/expression.pyx exposes this.