Re: [sage-devel] Category for IntegerModRing(n)
Hi! By lack of decision for the moment, I postponed the change to a later ticket, I just uploaded on trac a minimal version of my patch which just lets IntegerModRing use its categories, without upgrading its category to Fields(): see http://trac.sagemath.org/sage_trac/ticket/8562 which needs review. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org To unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
Re: [sage-devel] Category for IntegerModRing(n)
On Sat, Mar 20, 2010 at 04:35:01PM +0100, Florent hivert wrote: Hi There, In order to let Rob use IntegerModRing(n) as example of finite additive group for his cool Cayley graph feature (#7555), I just wrote a patch (#8562) letting IntegerModRing(n) use the category framework. That was essentially a one liner, plus minor updates here and there, and all test pass. [...] The Mod call constructs IntegerModRing(2^9941) and the primality test triggers a timeout or pari overflow. What strategy would you recommend? (1) We don't care about the usecase above (hmm) (2) IntegerModRing(n) is always in CommutativeRings() (3) Same thing, unless the user specifies the category: IntegerModRing(5, Fields()) You probably mean IntegerModRing(5, category=Fields()) which is consitent with was we do in sevaral other places. Yes. Although in that case, he might as well call GF(5). (4) IntegerModRing(n) always do a primality test, unless the user specifies himself the category. (5) When n is not too big, IntegerModRing(n) checks the primality of n, and sets the category accordingly. Otherwise it always uses CommutativeRings(). (6) When n is not too big, IntegerModRing(n) checks the primality of n, and returns GF(n) or a plain IntegerModRing(n) accordingly. What about: (6') if the user specifies a category with IntegerModRing(5, category=Fields()) then trust him and do no check otherwise (6). But maybe it is what you meant. That would be a 5', but yes indeed. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org To unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
Re: [sage-devel] Category for IntegerModRing(n)
On Sat, Mar 20, 2010 at 03:50:43PM +, John Cremona wrote: There are surely many other similar situations, for example when constructing a commutative ring it might be expensive to determine whether or not it is an Integral Domain. Yup. I would always use GF(p) rather than IntegerMod(p) for when I know p is prime. it is is vital in teaching primality tests and the like that one can form IntegerModRing(n) without knowing (or automatically testing behind the scenes) whether or not n is prime. Here is a typical situation where this feature could be desirable: Imagine that, in some deep construction, you construct internally a Z/nZ, without knowing in advance whether n is prime or not; then later on, you build some module M over it, and do some intensive linear algebra over it. Then you would want the linear algebra to automatically make use of the fact that M is a vector space for faster calculations. The first option is for the caller to do the primality test himself; but I find this a bit invasive (I need to know something about Z/nZ to do this); there might be similar situations where the test to be used could be less trivial. Another option is something like: IntegerModRing(n, category=best_possible) Alternatively, since it was pointed out that, given the name, it could be surprising for IntegerModRing to return a field (unless asked for explicitly), an option would be to leave IntegerModRing as is, and on the other hand, to have the current: Integers(5) return GF(5) automatically. (which exploits the optimized Givaro implementation) Best, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org To unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
[sage-devel] Category for IntegerModRing(n)
Hi! In order to let Rob use IntegerModRing(n) as example of finite additive group for his cool Cayley graph feature (#7555), I just wrote a patch (#8562) letting IntegerModRing(n) use the category framework. That was essentially a one liner, plus minor updates here and there, and all test pass. There is just a single issue for which I would like feedback. Namely, what shall be the result of: sage: IntegerModRing(5).category() It used to be CommutativeRings(), which feels a bit disappointing. So the current patch whether n is prime, and if yes sets the category to Fields(). This sounds natural, but there is one drawback: the category needs to be set at construction time, and the primality test can possibly be costly. And indeed, the Sage tests contain one use case where this is not acceptable (sage/tests/book_stein_ent.py, l.122): sage: def is_prime_lucas_lehmer(p): ...s = Mod(4, 2^p - 1) ...for i in range(3, p+1): ...s = s^2 - 2 ...return s == 0 sage: # Check primality of 2^9941 - 1 sage: is_prime_lucas_lehmer(9941) True The Mod call constructs IntegerModRing(2^9941) and the primality test triggers a timeout or pari overflow. What strategy would you recommend? (1) We don't care about the usecase above (hmm) (2) IntegerModRing(n) is always in CommutativeRings() (3) Same thing, unless the user specifies the category: IntegerModRing(5, Fields()) Although in that case, he might as well call GF(5). (4) IntegerModRing(n) always do a primality test, unless the user specifies himself the category. (5) When n is not too big, IntegerModRing(n) checks the primality of n, and sets the category accordingly. Otherwise it always uses CommutativeRings(). (6) When n is not too big, IntegerModRing(n) checks the primality of n, and returns GF(n) or a plain IntegerModRing(n) accordingly. (7) Something else? I vote for (6), but only with a very light preference. Thanks! Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org To unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
Re: [sage-devel] Category for IntegerModRing(n)
Hi There, In order to let Rob use IntegerModRing(n) as example of finite additive group for his cool Cayley graph feature (#7555), I just wrote a patch (#8562) letting IntegerModRing(n) use the category framework. That was essentially a one liner, plus minor updates here and there, and all test pass. [...] The Mod call constructs IntegerModRing(2^9941) and the primality test triggers a timeout or pari overflow. What strategy would you recommend? (1) We don't care about the usecase above (hmm) (2) IntegerModRing(n) is always in CommutativeRings() (3) Same thing, unless the user specifies the category: IntegerModRing(5, Fields()) You probably mean IntegerModRing(5, category=Fields()) which is consitent with was we do in sevaral other places. Although in that case, he might as well call GF(5). (4) IntegerModRing(n) always do a primality test, unless the user specifies himself the category. (5) When n is not too big, IntegerModRing(n) checks the primality of n, and sets the category accordingly. Otherwise it always uses CommutativeRings(). (6) When n is not too big, IntegerModRing(n) checks the primality of n, and returns GF(n) or a plain IntegerModRing(n) accordingly. What about: (6') if the user specifies a category with IntegerModRing(5, category=Fields()) then trust him and do no check otherwise (6). But maybe it is what you meant. Cheers, Florent -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org To unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
Re: [sage-devel] Category for IntegerModRing(n)
I would say that you should never test for primality unless specifically required, e.g. if the user asks is_field() (after which the category could be upgraded? I don't know if that is possible). I would always use GF(p) rather than IntegerMod(p) for when I know p is prime. it is is vital in teaching primality tests and the like that one can form IntegerModRing(n) without knowing (or automatically testing behind the scenes) whether or not n is prime. There are surely many other similar situations, for example when constructing a commutative ring it might be expensive to determine whether or not it is an Integral Domain. John PS This would be a suitable discussion for the newly-formed sage-algebra list! On 20 March 2010 15:35, Florent Hivert florent.hiv...@univ-rouen.fr wrote: Hi There, In order to let Rob use IntegerModRing(n) as example of finite additive group for his cool Cayley graph feature (#7555), I just wrote a patch (#8562) letting IntegerModRing(n) use the category framework. That was essentially a one liner, plus minor updates here and there, and all test pass. [...] The Mod call constructs IntegerModRing(2^9941) and the primality test triggers a timeout or pari overflow. What strategy would you recommend? (1) We don't care about the usecase above (hmm) (2) IntegerModRing(n) is always in CommutativeRings() (3) Same thing, unless the user specifies the category: IntegerModRing(5, Fields()) You probably mean IntegerModRing(5, category=Fields()) which is consitent with was we do in sevaral other places. Although in that case, he might as well call GF(5). (4) IntegerModRing(n) always do a primality test, unless the user specifies himself the category. (5) When n is not too big, IntegerModRing(n) checks the primality of n, and sets the category accordingly. Otherwise it always uses CommutativeRings(). (6) When n is not too big, IntegerModRing(n) checks the primality of n, and returns GF(n) or a plain IntegerModRing(n) accordingly. What about: (6') if the user specifies a category with IntegerModRing(5, category=Fields()) then trust him and do no check otherwise (6). But maybe it is what you meant. Cheers, Florent -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org To unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject. -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org To unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
Re: [sage-devel] Category for IntegerModRing(n)
On 20-Mar-10, at 8:50 AM, John Cremona wrote: I would say that you should never test for primality unless specifically required, e.g. if the user asks is_field() (after which the category could be upgraded? I don't know if that is possible). I would always use GF(p) rather than IntegerMod(p) for when I know p is prime. it is is vital in teaching primality tests and the like that one can form IntegerModRing(n) without knowing (or automatically testing behind the scenes) whether or not n is prime. There are surely many other similar situations, for example when constructing a commutative ring it might be expensive to determine whether or not it is an Integral Domain. +1, I agree with John: no primality testing unless I ask for it, and even then I would like to be able to specify the category and override it. Nick -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org To unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
