Opened 10 years ago

Closed 10 years ago

#11750 closed defect (fixed)

CRT_list not working for non-coprime moduli

Reported by: mderickx Owned by: tbd
Priority: major Milestone: sage-4.7.2
Component: basic arithmetic Keywords:
Cc: Merged in: sage-4.7.2.alpha3
Authors: Maarten Derickx Reviewers: Luis Felipe Tabera Alonso, Wai Yan Pong, Leif Leonhardy
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by leif)

sage: CRT([32,2,2],[60,90,150]) 


Traceback (click to the left of this block for traceback) 
... 
ValueError: No solution to crt problem since gcd(5400,150) does not 
divide 92-2 

Apply CRT_list-bugfix.patch to the Sage library.

Attachments (2)

CRT_list-bugfix.patch (1.4 KB) - added by mderickx 10 years ago.
cmdlinetestout.txt (1.3 KB) - added by pong 10 years ago.

Download all attachments as: .zip

Change History (24)

comment:1 Changed 10 years ago by mderickx

  • Status changed from new to needs_review

comment:2 Changed 10 years ago by lftabera

  • Status changed from needs_review to needs_work

Doctest fails, at least for additive abelian groups

sage -t "devel/sage-main/sage/groups/additive_abelian/additive_abelian_group.py"

AttributeError?: 'int' object has no attribute 'lcm'

The method does not work if the entries are ints or longs

sage: CRT([32r,2r,2r],[60r,90r,150r]) ... AttributeError?: 'int' object has no attribute 'lcm'

comment:3 Changed 10 years ago by kcrisman

  • Authors set to Maarten Derickx
  • Component changed from PLEASE CHANGE to basic arithmetic
  • Reviewers set to Luis Tabera
  • Type changed from PLEASE CHANGE to defect

comment:4 Changed 10 years ago by pong

The problem

sage: CRT([32r,2r,2r],[60r,90r,150r]) ... AttributeError??: 'int' object has no attribute 'lcm'

can easily be fixed by changing

m = m.lcm(moduli[i]) to

m = lcm(m,moduli[i])

in Maarten's patch. Perhaps, Maarten can issue an update on his patch.

comment:5 Changed 10 years ago by mderickx

Haha, I beat you pong. I already updated the patch as you said before you finnished your comment ;).

Running tests now again on sage.math this time not only the rings section before I put it into needs review again.

comment:6 Changed 10 years ago by pong

Good job, Marrten!

I was thinking of updating the patch, but realized that you will be much more efficient in doing so than me :-)

comment:7 Changed 10 years ago by mderickx

  • Status changed from needs_work to needs_review

And you where right apparently, but you don't have to worry about efficiency because you would have probably learnt more from it than me (i.e. there was a time when I was also still figuring stuff out).

You could still review the patch that's also usefull. It passed all tests for me on sage.math

comment:8 Changed 10 years ago by kcrisman

  • Reviewers changed from Luis Tabera to Luis Tabera, Wai Yan Pong

Pong, you are dangerously close to becoming a Sage developer! I'm putting you on as a reviewer ;-) make sure I spelled it right. Welcome aboard!

comment:9 Changed 10 years ago by leif

Patch looks reasonable. I don't think we need a reference to this ticket in the doctests, but a sentence added to the new example wouldn't be bad.

I only wonder nobody mentioned the typo(?) in both the ticket's title and the commit message; we don't support compressed moduli now, but ones that aren't co-prime (or coprime) to each other. (Never heard "comprime" in that context, but perhaps it's just me.)

Changed 10 years ago by mderickx

comment:10 Changed 10 years ago by mderickx

  • Summary changed from CRT_list not working for non comprime moduli to CRT_list not working for non coprime moduli

It was indeed a typo of me. Added a new patch.

ps. Leif, next time when adding a review like comment to a ticket either put it into needs_work or positive_review or say that you are not done yet with the review or something. Right now it was not really clear what you expected to happen.

comment:11 follow-up: Changed 10 years ago by leif

  • Reviewers changed from Luis Tabera, Wai Yan Pong to Luis Felipe Tabera Alonso, Wai Yan Pong, Leif Leonhardy
  • Status changed from needs_review to positive_review
  • Summary changed from CRT_list not working for non coprime moduli to CRT_list not working for non-coprime moduli

Ok, although I would have written something like

"But if some of the moduli have non-trivial common divisors there is not always a solution:"

(otherwise non coprime should have a hyphen in it, but that's IMHO a minor issue).

So positive review from me. (Feel free to revert this in case you disagree or want to change the patch again.)


P.S.:

I left the ticket as "needs review" since I expected some response from any of the author(s) or other reviewers (i.e., their opinion). Since it was still needing review anyway, I didn't set it to "needs info".

If I had been 100% sure about "comprime" being a typo, I would have set it to "needs work" of course (and changed the ticket's title myself). Adding an explanatory sentence to the new example was just a suggestion, of IMO minor importance.


P.P.S.: Jeroen requested us to use unique (i.e. full) names in the "Author(s)" and "Reviewer(s)" fields, so I changed Luis' according to his wiki list entry.

comment:12 in reply to: ↑ 11 Changed 10 years ago by kcrisman

P.P.S.: Jeroen requested us to use unique (i.e. full) names in the "Author(s)" and "Reviewer(s)" fields, so I changed Luis' according to his wiki list entry.

That's my bad, I was just doing it from memory. My apologies; I try to be detail-oriented with such things as well.

comment:13 Changed 10 years ago by pong

I'm new to the patch-reviewing process and am working on it now (following the steps in the sage developer gulide). KDC thanks for including me in the loop.

comment:14 follow-up: Changed 10 years ago by pong

Here is my review:

1) The patch is correct. 2) when I ran ./sage --testall --long it complained about cmdline.py

sage -t --long -force_lib "devel/sage/sage/tests/cmdline.py" there are 4 failures. But I suspect they have nothing to do with this patch.

3) ./sage -coverage devel/sage-test/sage/rings/arith.py produces


devel/sage-test/sage/rings/arith.py ERROR: Please add a TestSuite(s).run() doctest. SCORE devel/sage-test/sage/rings/arith.py: 100% (89 of 89)


It scores a 100% but should we worry about the "ERROR" above?

Anyway, I leave it as positive_review. And I hope someone can educate me on item 2) and 3) above. Thanks.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 10 years ago by leif

Replying to pong:

Here is my review:

1) The patch is correct.
2) when I ran ./sage --testall --long it complained about cmdline.py

sage -t --long -force_lib "devel/sage/sage/tests/cmdline.py"
there are 4 failures. But I suspect they have nothing to do with this patch.

Perhaps add on what system / platform you tested, and with which version of Sage.

Also, it wouldn't be bad to know how the tests actually failed. ;-)


make testlong passed all tests on Ubuntu 10.04.3 x86_64 (Core2, gcc 4.5.1) with Sage 4.7.2.alpha2.

comment:16 Changed 10 years ago by mderickx

Could you please run sage -t --long -force_lib "devel/sage/sage/tests/cmdline.py with and without the patch applied and show the output so we know what exactly is going on?

The error in 3 means that the arith.py module doesn't have a TestSuite? yet. When the current category framework was introduced it was decided that every module should also have a TestSuite? to get even better testing then the current doctest framework. Of course there is a long road between deciding that something has to be there and adding it for every module in sage.

This error should not be ignored when someone writes a new module or practically rewrites an entire module.

comment:17 in reply to: ↑ 15 Changed 10 years ago by leif

Replying to leif:

make testlong passed all tests on Ubuntu 10.04.3 x86_64 (Core2, gcc 4.5.1) with Sage 4.7.2.alpha2.

Ooops, actually Sage 4.7.2.alpha1.

alpha2 is still building...

Changed 10 years ago by pong

comment:18 follow-up: Changed 10 years ago by pong

Unfortunately, on my local machine I've already applied the patch to the main branch. The output of sage -t --long -force_lib "devel/sage/sage/tests/cmdline.py is attached above

On the other hand, on my dept server the same test passed before applying the patch. However, when I try to apply the patch, it complains

RuntimeError?: Refusing to do operation since you still have unrecorded changes. You must check in all changes in your working repository first.

Hum... I don't know how to handle that. N.B. We have tried using the flask notebook but then decided not using it on the server, so that maybe the cause of the error above.

Sorry for stating and unrelated problem (to this patch) but that's what I encountered during the test.

comment:19 in reply to: ↑ 18 Changed 10 years ago by leif

Replying to pong:

Unfortunately, on my local machine I've already applied the patch to the main branch. The output of sage -t --long -force_lib "devel/sage/sage/tests/cmdline.py is attached above

You can do the following to unapply the patch:

~/Sage/sage-4.7.2.alpha1/devel/sage$ hg log | head -15
changeset:   15994:b0440a76e01f
tag:         tip
user:        Maarten Derickx <m.derickx.student@gmail.com>
date:        Fri Aug 26 11:41:55 2011 -0700
summary:     11750 fix CRT_list for non coprime moduli

changeset:   15993:6d083e3d29a3
user:        Jeroen Demeyer <jdemeyer@cage.ugent.be>
date:        Wed Aug 17 16:07:36 2011 +0000
summary:     4.7.2.alpha1

changeset:   15992:5a8bb5f7dbef
user:        Jeroen Demeyer <jdemeyer@cage.ugent.be>
date:        Wed Aug 17 12:37:58 2011 +0000
summary:     Added tag 4.7.2.alpha1 for changeset aee2c735d079

Take the revision number (currently 5 digits) of the changeset right before you applied the patch, and then do

~/Sage/sage-4.7.2.alpha1/devel/sage$ hg update -r <number> # 15993 in this case
...
~/Sage/sage-4.7.2.alpha1/devel/sage$ ../../sage -b # rebuild the Sage library
...

Then you can rerun tests without the patch.

Try e.g. hg help update for further options.

comment:20 Changed 10 years ago by pong

Okay

1) On my department server sage -t --long -force_lib "devel/sage/sage/tests/cmdline.py passes with or without the patch being applied.

2) On my local machine the same test fails in both cases.

So we don't need to worry for this patch (although I appreciate for any suggestion on how to fix that on my own machine).

I give my positive review to the patch.

comment:21 Changed 10 years ago by leif

  • Description modified (diff)

comment:22 Changed 10 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.