CRT_list not working for non-coprime moduli

[koffie]

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 attachment: CRT_list-bugfix.patch to the Sage library.

Component: basic arithmetic

Author: Maarten Derickx

Reviewer: Luis Felipe Tabera Alonso, Wai Yan Pong, Leif Leonhardy

Merged: sage-4.7.2.alpha3

Issue created by migration from https://trac.sagemath.org/ticket/11750

[lftabera]

comment:2

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'

[kcrisman]

Author: Maarten Derickx

[kcrisman]

Reviewer: Luis Tabera

[wypong]

comment:4

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.

[koffie]

comment:5

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.

[wypong]

comment:6

Good job, Marrten!

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

[koffie]

comment:7

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

[kcrisman]

Changed reviewer from Luis Tabera to Luis Tabera, Wai Yan Pong

[kcrisman]

comment:8

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!

[nexttime]

comment:9

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.)

[koffie]

comment:10

Attachment: CRT_list-bugfix.patch.gz

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.

[nexttime]

Changed reviewer from Luis Tabera, Wai Yan Pong to Luis Felipe Tabera Alonso, Wai Yan Pong, Leif Leonhardy

[nexttime]

comment:11

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.

[kcrisman]

comment:12

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.

[wypong]

comment:13

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.

[wypong]

comment:14

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.

[nexttime]

comment:15

Replying to @wypong:

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.

[koffie]

comment:16

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.

[nexttime]

comment:17

Replying to @nexttime:

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...

[wypong]

Attachment: cmdlinetestout.txt

[wypong]

comment:18

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.

[nexttime]

comment:19

Replying to @wypong:

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.

[wypong]

comment:20

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.

[nexttime]

Merged: sage-4.7.2.alpha3