[sage-devel] Re: Conway's nimber field
Yes the basic reference is ONAG. I will put a more precise
reference in the source (but I need to go to the library
to fetch ONAG). Basically the two rules for multiplying
nimbers are
(1) The product of any number of distinct Fermat powers
is the ordinary product.
(2) If f is a Fermat power then f^2=3f/2 (where 3f/2 is
computed for the ordinary product).
Basically (1)(2) say that if f_n is the n't Fermat power then
f_n^2=f_n+f_{n-1}f_{n-2}...f_0
This realizes the nimber field as a tower of quadratic extensions.
To compute in the nimber field we write nimbers f^2 (f a Fermat
power) as l*f+r with l,rf and work recursively.
Michel
On 19 mrt, 21:29, David Joyner [EMAIL PROTECTED] wrote:
Are you using ONAG for the main reference? In any case, I would appreciate
a precise reference to a book or article on nimbers.
On 3/19/07, Michel [EMAIL PROTECTED] wrote:
Hi,
To acquant myself with sage's inner workings I have implemented
Conway's nimber field.
See
http://alpha.uhasselt.be/Research/Algebra/Members/nimbers/
Recall that the nimbers form a field whose underlying set is the
natural numbers. The addition is bitwise exclusive or but the
multiplication is complicated. GF(2^(2^n)) is isomorphic to the
nimbers that are less than 2^(2^n). Thus the full nimber field is
isomorphic to the union of GF(2^(2^n)) for all n.
Although my implenentation is still in pure python it seems to be not
much slower
than the standard finite fields GF(2^(2^n)) that one can create in
sage. However I didn't
do extensive testing. The basic arithmetic should be trivial to
rewrite in pyrex.
This is still a prototype. The most glaring ommission is that
coercions from and to
standard Galois fields are missing. Nevertheless if there are remarks/
comments I would
appreciate it very much.
Regards,
Michel
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: Biopython package
Great! I am once again amazed by your speed. I set SAGE_SERVER as you said, but my attempt at installing fails to get the package. The output is appended below. I doing this on a PPC (G4) Apple powerbook, with sage 2.0 upgraded to 2.3. I had tried to read the documentation you suggested - I was only volunteering to try this because it seemed relatively simple! I've installed biopython 1.42 on linux, apple, and windows machines, but I haven't tried a normal install of 1.43 yet (its quite recent). I am not sure what mxTextTools is doing; in a python install I just do 'sudo python setup.py install' although I am not sure that the sudo is necessary. I'll also give this a try on the Mac Pro (Intel) in my office when I get in. Thanks, Marshall ~/sage-2.0:07:43:42:./sage -i biopython-1.43 Installing biopython-1.43 Calling sage-spkg on biopython-1.43 WARNING: Using SAGE_ROOT variable that was already set to '/Users/mh/ sage-2.0'. biopython-1.43 Machine: Darwin medmgmt-3.tajen.edu.tw 8.8.0 Darwin Kernel Version 8.8.0: Fri Sep 8 17:18:57 PDT 2006; root:xnu-792.12.6.obj~1/RELEASE_PPC Power Macintosh powerpc Deleting directories from past builds of previous/current versions of biopython-1.43 /Users/mh/sage-2.0/local/bin/sage-spkg: file /Users/mh/sage-2.0/ biopython-1.43 does not exist Attempting to download it. www.sagemath.org/packages/optional/biopython-1.43.spkg -- biopython-1.43.spkg [ Traceback (most recent call last): File /Users/mh/sage-2.0/local/bin/sage-download_package, line 53, in module if not download_file(optional/%s%F): File /Users/mh/sage-2.0/local/bin/sage-download_package, line 45, in download_file urllib.urlretrieve(url, file, reporthook) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 89, in urlretrieve return _urlopener.retrieve(url, filename, reporthook, data) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 222, in retrieve fp = self.open(url, data) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 190, in open return getattr(self, name)(url) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 451, in open_file return self.open_local_file(url) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 465, in open_local_file raise IOError(e.errno, e.strerror, e.filename) IOError: [Errno 2] No such file or directory: 'www.sagemath.org/ packages/optional/biopython-1.43.spkg' sage: Failed to download package biopython-1.43 from www.sagemath.org On Mar 19, 10:52 pm, William Stein [EMAIL PROTECTED] wrote: On Monday 19 March 2007 8:28 pm, Hamptonio wrote: Hi, I became interested in SAGE after I found it to be the easiest way to install cddlib and gmp, and now I am getting hooked. My research is very schizophrenic: besides some computational algebra/geometry coming from dynamical systems, I am also interested in mathematical biology and bioinformatics. There is an open-source project called biopython (http://biopython.org/wiki/Biopython) that I am using in a bioinformatics course right now. It would be very nice if there was a biopython optional package for SAGE. I am willing to try and create one, but I thought I would post here first to see if anyone had any preliminary advice before I waste my time. Biopython currently requires Numeric, but all the parts I need seem to work OK using numpy. The developers are currently working on switching over entirely to numpy. It also requires something called mxTextTools, but I think that should be OK since its open source and has a very permissive license. Adding biopython is a good idea. Prompted by your email, I created a package for it, which I've posted here: http://www.sagemath.org/packages/optional/ If you do $ export SAGE_SERVER=www.sagemath.org from bash, you can get it with sage -i biopython-1.43 My biophython-1.43 package includes mxTextTools, so it's very easy to install. Also, it seems that biophython-1.43 works fine with numpy. If it doesn't, Numeric is a well-supported optional sage package: sage -i numeric-24.2. One very annoying thing that somebody needs to get to the bottom of, is that it seems necessary to hit enter several times half-way through the install, or it just pauses forever. This probably has something to do with maybe mxTextTools's installing doing something obnoxious. Feedback is appreciated. By the way, this document gives a basic idea of how spkg's are created: http://www.sagemath.com/doc/html/prog/node23.html In short, an spkg is just a bzip2'd tarball, with a file spkg-install that gets run in the environment of SAGE, e.g., python is SAGE's Python, etc., and it is supposed to install code to $SAGE_LOCAL. William William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at
[sage-devel] Re: Biopython package
Woo-hoo! Thank you!!! I had the same error as before on my Mac Pro - the '... in open_local_file raise IOError(e.errno, e.strerror, e.filename) IOError: [Errno 2] No such file or directory: 'www.sagemath.org/ packages/optional/biopython-1.43.spkg' sage: Failed to download package biopython-1.43 from www.sagemath.org' error, so I manually downloaded the spkg from www.sagemath.org, and it installed fine apart from the weird need for 'enter' commands that you warned me about. I have tested a few of my more commonly used tasks and it seems to work. I can tell the biopython developers about this once the package download problems get a little sorted out. Thanks again, Marshall On Mar 20, 7:53 am, Hamptonio [EMAIL PROTECTED] wrote: Great! I am once again amazed by your speed. I set SAGE_SERVER as you said, but my attempt at installing fails to get the package. The output is appended below. I doing this on a PPC (G4) Apple powerbook, with sage 2.0 upgraded to 2.3. I had tried to read the documentation you suggested - I was only volunteering to try this because it seemed relatively simple! I've installed biopython 1.42 on linux, apple, and windows machines, but I haven't tried a normal install of 1.43 yet (its quite recent). I am not sure what mxTextTools is doing; in a python install I just do 'sudo python setup.py install' although I am not sure that the sudo is necessary. I'll also give this a try on the Mac Pro (Intel) in my office when I get in. Thanks, Marshall ~/sage-2.0:07:43:42:./sage -i biopython-1.43 Installing biopython-1.43 Calling sage-spkg on biopython-1.43 WARNING: Using SAGE_ROOT variable that was already set to '/Users/mh/ sage-2.0'. biopython-1.43 Machine: Darwin medmgmt-3.tajen.edu.tw 8.8.0 Darwin Kernel Version 8.8.0: Fri Sep 8 17:18:57 PDT 2006; root:xnu-792.12.6.obj~1/RELEASE_PPC Power Macintosh powerpc Deleting directories from past builds of previous/current versions of biopython-1.43 /Users/mh/sage-2.0/local/bin/sage-spkg: file /Users/mh/sage-2.0/ biopython-1.43 does not exist Attempting to download it.www.sagemath.org/packages/optional/biopython-1.43.spkg-- biopython-1.43.spkg [ Traceback (most recent call last): File /Users/mh/sage-2.0/local/bin/sage-download_package, line 53, in module if not download_file(optional/%s%F): File /Users/mh/sage-2.0/local/bin/sage-download_package, line 45, in download_file urllib.urlretrieve(url, file, reporthook) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 89, in urlretrieve return _urlopener.retrieve(url, filename, reporthook, data) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 222, in retrieve fp = self.open(url, data) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 190, in open return getattr(self, name)(url) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 451, in open_file return self.open_local_file(url) File /Users/mh/sage-2.0/local/lib/python2.5/urllib.py, line 465, in open_local_file raise IOError(e.errno, e.strerror, e.filename) IOError: [Errno 2] No such file or directory: 'www.sagemath.org/ packages/optional/biopython-1.43.spkg' sage: Failed to download package biopython-1.43 fromwww.sagemath.org On Mar 19, 10:52 pm, William Stein [EMAIL PROTECTED] wrote: On Monday 19 March 2007 8:28 pm, Hamptonio wrote: Hi, I became interested in SAGE after I found it to be the easiest way to install cddlib and gmp, and now I am getting hooked. My research is very schizophrenic: besides some computational algebra/geometry coming from dynamical systems, I am also interested in mathematical biology and bioinformatics. There is an open-source project called biopython (http://biopython.org/wiki/Biopython) that I am using in a bioinformatics course right now. It would be very nice if there was a biopython optional package for SAGE. I am willing to try and create one, but I thought I would post here first to see if anyone had any preliminary advice before I waste my time. Biopython currently requires Numeric, but all the parts I need seem to work OK using numpy. The developers are currently working on switching over entirely to numpy. It also requires something called mxTextTools, but I think that should be OK since its open source and has a very permissive license. Adding biopython is a good idea. Prompted by your email, I created a package for it, which I've posted here: http://www.sagemath.org/packages/optional/ If you do $ export SAGE_SERVER=www.sagemath.org from bash, you can get it with sage -i biopython-1.43 My biophython-1.43 package includes mxTextTools, so it's very easy to install. Also, it seems that biophython-1.43 works fine with numpy. If it doesn't, Numeric is a well-supported optional sage package: sage -i numeric-24.2. One very annoying thing that somebody needs to get to
[sage-devel] Re: Biopython package
On Mar 20, 2007, at 09:30 , Hamptonio wrote: Just to clarify: the downloading problem isn't biopython-specific - I can't get anything from www.sagemath.org through sage, only from a browser. For example, 'sage -optional' fails as well. www.sagemath.org seems to be down for the count. I'm getting no response to pings. Justin -- Justin C. Walker, Curmudgeon-At-Large Institute for the Absorption of Federal Funds Men are from Earth. Women are from Earth. Deal with it. --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] good news: 16 cores on sage.math
Hi, Good news -- I took this downtime as a chance to install RHEL (Redhat Enterprise Linux) on sage.math.washington.edu. By default it booted up with a kernel that works and correctly recognizes all SIXTEEN cores on sage.math. So now sage.math is twice as super, since before with Ubuntu only 8 cores were recognized with any kernel I could get to boot. -- William -- William Stein Associate Professor of Mathematics University of Washington --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Inconsistency in root finding
On Tuesday 20 March 2007 4:00 pm, Nick Alexander wrote: For some reason, google won't let me grab your patch. Anyway, converting to string is not a good idea. Better to hash a tuple of real, imag I think. (Maybe you did this already?) You have to be really careful, since if a == b, then one should strive very hard to have hash(a) == hash(b). Thus, e.g., if a is a real and b is a complex number with real part a and imaginary part 0, if you hash the strings then you get equality of the hashes, but if you hash the tuple you don't. That said, I don't think hashing the strings it the right approach, since it is slow and requires converting to base 10, which sucks. In real_mpfi.pyx, Carl Witty did this, which is better than hash(str(self)): def __hash__(self): return hash(self.str(16)) I don't seem able to send in a key function sorted; I'll try sort(cmp=) in a moment. I wonder if I hit a Pyrex bug? Possibly. You might have to move the relevant code snippet to Python or use eval, or at least post a minimal example to this list. William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Bug in coercion to pari?
My guess is that the pari conversion code is not being careful with the variable names, but I haven't really tried it. Makes it pretty hard to work with number fields, no? Nick sage: (QQ['x'].0^2 + 1).is_irreducible() True sage: (QQ['a'].0^2 + 1).is_irreducible() --- type 'exceptions.NotImplementedError' Traceback (most recent call last) /Users/nalexand/emacs/sage/ipython console in module() /Users/nalexand/emacs/sage/polynomial_element.pyx in polynomial_element.Polynomial.is_irreducible() /Users/nalexand/emacs/sage/polynomial_element.pyx in polynomial_element.Polynomial.factor() type 'exceptions.NotImplementedError': /Users/nalexand/emacs/sage/polynomial_element.pyx(987)polynomial_element.Polynomial.factor() --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Bug in coercion to pari?
On 3/20/07, Nick Alexander [EMAIL PROTECTED] wrote: My guess is that the pari conversion code is not being careful with the variable names, but I haven't really tried it. Makes it pretty hard to work with number fields, no? Nick sage: (QQ['x'].0^2 + 1).is_irreducible() True sage: (QQ['a'].0^2 + 1).is_irreducible() --- type 'exceptions.NotImplementedError' Traceback (most recent call last) I don't know what email you're responding to or what version of SAGE you're using, but the above example works fine for me (no error) with sage-2.3: rank4:~ was$ sage -- | SAGE Version 2.3, Release Date: 2007-03-06 | | Type notebook() for the GUI, and license() for information.| -- sage: (QQ['a'].0^2 + 1).is_irreducible() True the pari conversion code is not being careful with the variable names, but I haven't really tried it. Makes it pretty hard to work with number fields, no? Regarding that comment, you have to be very very careful with coercing to PARI -- in particular you often do *not* want to preserve the variable name, since in PARI certain natural variables names (which you would want to use in SAGE) do not work like you might think they would. Also, the actual variable name has an impact sometimes on how it behaves in PARI, e.g., x is different than t in some contexts. For example, sage: pari(QQ['I'].0) class 'gen.PariError' Traceback (most recent call last) ... class 'gen.PariError': (8) sage: (QQ['I'].0^2 + 1).is_irreducible() True As you can see, you do not want to just coerce the polynomial to PARI when doing the irreducibility test, since, e.g., the variable named I isn't allowed in PARI. William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] factorization in multivariable polynomial ring
how hard would it be to make this work? W.w1,w2 = ZZ['w1','w2'] factor(w1*w2) big traceback i'm using sage 2.3. if somebody could send me a code snippet, it would be hugely appreciated. kyle --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: factorization in multivariable polynomial ring
On 3/20/07, Kyle Schalm [EMAIL PROTECTED] wrote: how hard would it be to make this work? W.w1,w2 = ZZ['w1','w2'] factor(w1*w2) big traceback i'm using sage 2.3. if somebody could send me a code snippet, it would be hugely appreciated. Work over QQ instead: sage: W.w1,w2 = QQ['w1','w2'] sage: factor(w1*w2) w2 * w1 One can reduce factoring over ZZ to over QQ, with some work. Volunteers...? William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: factorization in multivariable polynomial ring
Work over QQ instead: sage: W.w1,w2 = QQ['w1','w2'] sage: factor(w1*w2) w2 * w1 One can reduce factoring over ZZ to over QQ, with some work. Volunteers...? William oh good, an easy workaround. the same trick doesn't seem to work if the base ring is a polynomial ring, that is, replacing it with its fraction field still doesn't work. but your workaround will do for now. thanks. kyle --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: factorization in multivariable polynomial ring
On Tuesday 20 March 2007 5:30 pm, Kyle Schalm wrote: Work over QQ instead: sage: W.w1,w2 = QQ['w1','w2'] sage: factor(w1*w2) w2 * w1 One can reduce factoring over ZZ to over QQ, with some work. Volunteers...? William oh good, an easy workaround. the same trick doesn't seem to work if the base ring is a polynomial ring, that is, replacing it with its fraction field still doesn't work. but your workaround will do for now. thanks. Presumably one can do this case too by: (1) clearing denominators, (2) working in a polynomial ring in all the variables, (3) and choosing a suitable term ordering on the indeterminantes, then (4) factoring in the bigger poly ring. Again, if somebody ones to make this work natively (without the user having to know any tricks), a patch would be welcome. William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] determinant bug
there is trouble with the determinant method on a matrix over a funky ring (yes, the same funky ring causing all my other problems). in its simplest form: In [43]: W.w=QQ['w'] In [44]: WZ.z=W['z'] In [45]: matrix(WZ,2,2,[1,z,z,z^2]).det() Out[45]: kaboom!!! the analog over a shallower polynomial ring works: In [54]: matrix(W,2,2,[1,w,w,w^2]).det() Out[54]: 0 i've implemented a local workaround, but i wanted to make this bug report. (my workaround consists of wrapping the call to charpoly in a try...except block, and then falling through to the other code which does expansion by minors.) -kyle p.s. is there a more formal or preferred way to submit a bug report? --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: determinant bug
On 3/20/07, Kyle Schalm [EMAIL PROTECTED] wrote: there is trouble with the determinant method on a matrix over a funky ring (yes, the same funky ring causing all my other problems). in its simplest form: In [43]: W.w=QQ['w'] In [44]: WZ.z=W['z'] In [45]: matrix(WZ,2,2,[1,z,z,z^2]).det() Out[45]: kaboom!!! The attached patch fixes this. It's a one liner, so if you have trouble applying it, just look at it and make the change by hand, then do sage -br. It's not the right fix, though it is in no way wrong either; don't worry, in my personal codebase I've created a doctest that exposes the true problem that causes the issue above. p.s. is there a more formal or preferred way to submit a bug report? This is fine. You could also use trac: http://www.sagemath.org:9002/sage_trac but even then posting to sage-devel in addition would be a good idea. -- William Stein Associate Professor of Mathematics University of Washington --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~--- 3500.patch Description: Binary data
[sage-devel] Re: Inconsistency in root finding
On Mar 20, 4:12 pm, William Stein [EMAIL PROTECTED] wrote: On Tuesday 20 March 2007 4:00 pm, Nick Alexander wrote: For some reason, google won't let me grab your patch. Anyway, converting to string is not a good idea. Better to hash a tuple of real, imag I think. (Maybe you did this already?) You have to be really careful, since if a == b, then one should strive very hard to have hash(a) == hash(b). Thus, e.g., if a is a real and b is a complex number with real part a and imaginary part 0, if you hash the strings then you get equality of the hashes, but if you hash the tuple you don't. Hmm, it seems to me that this has deep implications. When hashing, one really needs to find the 'minimal representation' of the element. Suppose I want to hash QQ['x'](1), a constant polynomial. This should hash to the same thing as QQ(1) and ZZ(1), right? Same with (QQ['x']) ['y'](1), etc. And it gets more convoluted when you have more interesting extension fields. And what about quotients -- should Mod(1, 3) hash to the same thing as ZZ(1)? Should (QQ['x']/x^2+1)(1) hash to the hash of ZZ(1)? Should (QQ['x']/x^2+1)(x) has to the same thing as CC(I)? (For the record, I think the last one shouldn't happen, but for no strong reason.) In some sense, we've worked out the general case with the canonical coercion code. But this is not the same case: here, we want CC(1) to hash to RR(1), whereas there is no canonical coercion C to R. There are some conventions around __call__, maybe those hold the correct answer. Before I think more about this, do people agree that there are problems with the current situation? I am interested to know what will happen when hashing various elements of finite fields, extensions of finite fields, padic extensions, etc. Same with lattices of number fields over QQ and ZZ, and embeddings into CC. Nick --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Inconsistency in root finding
On Mar 21, 2007, at 1:19 AM, Nick Alexander wrote: On Mar 20, 4:12 pm, William Stein [EMAIL PROTECTED] wrote: On Tuesday 20 March 2007 4:00 pm, Nick Alexander wrote: For some reason, google won't let me grab your patch. Anyway, converting to string is not a good idea. Better to hash a tuple of real, imag I think. (Maybe you did this already?) You have to be really careful, since if a == b, then one should strive very hard to have hash(a) == hash(b). Thus, e.g., if a is a real and b is a complex number with real part a and imaginary part 0, if you hash the strings then you get equality of the hashes, but if you hash the tuple you don't. Hmm, it seems to me that this has deep implications. When hashing, one really needs to find the 'minimal representation' of the element. Suppose I want to hash QQ['x'](1), a constant polynomial. This should hash to the same thing as QQ(1) and ZZ(1), right? Same with (QQ['x']) ['y'](1), etc. And it gets more convoluted when you have more interesting extension fields. And what about quotients -- should Mod(1, 3) hash to the same thing as ZZ(1)? Should (QQ['x']/x^2+1)(1) hash to the hash of ZZ(1)? Should (QQ['x']/x^2+1)(x) has to the same thing as CC(I)? (For the record, I think the last one shouldn't happen, but for no strong reason.) In some sense, we've worked out the general case with the canonical coercion code. But this is not the same case: here, we want CC(1) to hash to RR(1), whereas there is no canonical coercion C to R. There are some conventions around __call__, maybe those hold the correct answer. Before I think more about this, do people agree that there are problems with the current situation? I am interested to know what will happen when hashing various elements of finite fields, extensions of finite fields, padic extensions, etc. Same with lattices of number fields over QQ and ZZ, and embeddings into CC. Oh boy I really really don't like where this is going. Insisting on a == b = hash(a) == hash(b) with sage's canonical coercion model seems really really bad. For example sage: Integers(123818273)(2394) == Integers(1)(0) True So then all integers mod n (for all n) have to hash to the same thing. Please let's not go there. David --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Inconsistency in root finding
On Mar 20, 2007, at 10:27 PM, David Harvey wrote: On Mar 21, 2007, at 1:19 AM, Nick Alexander wrote: On Mar 20, 4:12 pm, William Stein [EMAIL PROTECTED] wrote: On Tuesday 20 March 2007 4:00 pm, Nick Alexander wrote: For some reason, google won't let me grab your patch. Anyway, converting to string is not a good idea. Better to hash a tuple of real, imag I think. (Maybe you did this already?) You have to be really careful, since if a == b, then one should strive very hard to have hash(a) == hash(b). Thus, e.g., if a is a real and b is a complex number with real part a and imaginary part 0, if you hash the strings then you get equality of the hashes, but if you hash the tuple you don't. Hmm, it seems to me that this has deep implications. When hashing, one really needs to find the 'minimal representation' of the element. Suppose I want to hash QQ['x'](1), a constant polynomial. This should hash to the same thing as QQ(1) and ZZ(1), right? Same with (QQ ['x']) ['y'](1), etc. And it gets more convoluted when you have more interesting extension fields. And what about quotients -- should Mod(1, 3) hash to the same thing as ZZ(1)? Should (QQ['x']/x^2+1)(1) hash to the hash of ZZ(1)? Should (QQ['x']/x^2+1)(x) has to the same thing as CC(I)? (For the record, I think the last one shouldn't happen, but for no strong reason.) In some sense, we've worked out the general case with the canonical coercion code. But this is not the same case: here, we want CC(1) to hash to RR(1), whereas there is no canonical coercion C to R. There are some conventions around __call__, maybe those hold the correct answer. Before I think more about this, do people agree that there are problems with the current situation? I am interested to know what will happen when hashing various elements of finite fields, extensions of finite fields, padic extensions, etc. Same with lattices of number fields over QQ and ZZ, and embeddings into CC. Oh boy I really really don't like where this is going. Insisting on a == b = hash(a) == hash(b) with sage's canonical coercion model seems really really bad. For example sage: Integers(123818273)(2394) == Integers(1)(0) True So then all integers mod n (for all n) have to hash to the same thing. Please let's not go there. There's also the issue of precision, e.g. RDF(0) == RealField(1) (1), but sage: R = RealField(1) sage: a = R(1) + R(10)^-100 sage: a == RDF(1) but I don't think hash(a) should equal (necessarily) hash(1). If it seems natural (e.g. in this case where the coercion is R - C), however, I think it would be nice. One could also force all keys of a hashtable to live in a given ring. - Robert --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Inconsistency in root finding
On 3/20/07, David Harvey [EMAIL PROTECTED] wrote:
On Mar 21, 2007, at 1:19 AM, Nick Alexander wrote:
On Mar 20, 4:12 pm, William Stein [EMAIL PROTECTED] wrote:
On Tuesday 20 March 2007 4:00 pm, Nick Alexander wrote:
For some reason, google won't let me grab your patch. Anyway,
converting to string is not a good idea. Better to hash a tuple of
real, imag I think. (Maybe you did this already?)
You have to be really careful, since if a == b,
then one should strive very hard to have hash(a) == hash(b).
Thus, e.g.,
if a is a real and b is a complex number with real part a and
imaginary
part 0, if you hash the strings then you get equality of the
hashes, but
if you hash the tuple you don't.
Hmm, it seems to me that this has deep implications. When hashing,
one really needs to find the 'minimal representation' of the element.
Suppose I want to hash QQ['x'](1), a constant polynomial. This should
[...]
Oh boy I really really don't like where this is going. Insisting on
a == b = hash(a) == hash(b) with sage's canonical coercion model
seems really really bad.
For example
sage: Integers(123818273)(2394) == Integers(1)(0)
True
So then all integers mod n (for all n) have to hash to the same thing.
Please let's not go there.
Sorry, but we have to go there, again. This has been discussed
before more than once on this list. Here's the definition of __hash__
in the Python reference manual [1]
__hash__(self)
Called for the key object for dictionary operations, and by the
built-in function hash(). Should return a 32-bit integer usable as a
hash value for dictionary operations. The only required property is
that objects which compare equal have the same hash value; it is
advised to somehow mix together (e.g., using exclusive or) the hash
values for the components of the object that also play a part in
comparison of objects. If a class does not define a __cmp__() method
it should not define a __hash__() operation either; if it defines
__cmp__() or __eq__() but not __hash__(), its instances will not be
usable as dictionary keys. If a class defines mutable objects and
implements a __cmp__() or __eq__() method, it should not implement
__hash__(), since the dictionary implementation requires that a key's
hash value is immutable (if the object's hash value changes, it will
be in the wrong hash bucket).
Notice the The only required property is that objects which compare
equal have the same hash value. This is an assumption made by the
Python language, and violating has consequences. Fortunately, the
consequences are pretty clearly
defined and reasonably easy to understand, so if you know about them
they don't cause you trouble. I think the following example
illustrates them pretty well:
sage: v = [Mod(2,7)]
sage: 9 in v
True
sage: v = set([Mod(2,7)])
sage: 9 in v
False
sage: 2 in v
True
sage: w = {Mod(2,7):'a'}
sage: w[2]
'a'
sage: w[9]
Traceback (most recent call last):
...
KeyError: 9
---
That said, we simply can't require
(*) a == b == hash(a) == hash(b)
in SAGE, because mathematics is simply too complicated for this sort
of rule. So what is done in SAGE is to _attempt_ to satisfy (*) when it
is reasonably easy to do so, but use judgment and not go overboard.
E.g.,
sage: hash(Mod(2,7))
2
I.e., we get 2. That's better than some weird random hash that also
involves the moduli, but it's of course not right from the Python point
of view, since 9 == Mod(2,7). Long ago before we ever had this
discussion about hashing, I think Mod(2,7) was the hash of some
combination of 2 and 7.
Anyway, I hope this clarifies things for people.
[1] http://docs.python.org/ref/customization.html#l2h-196
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: Inconsistency in root finding
On Mar 21, 2007, at 1:38 AM, William Stein wrote: That said, we simply can't require (*) a == b == hash(a) == hash(b) in SAGE, because mathematics is simply too complicated for this sort of rule. So what is done in SAGE is to _attempt_ to satisfy (*) when it is reasonably easy to do so, but use judgment and not go overboard. E.g., sage: hash(Mod(2,7)) 2 I.e., we get 2. That's better than some weird random hash that also involves the moduli, but it's of course not right from the Python point of view, since 9 == Mod(2,7). Long ago before we ever had this discussion about hashing, I think Mod(2,7) was the hash of some combination of 2 and 7. The only way we could fix this problem for good is to abandon using the == operator for SAGE equality, and implement SAGE equality as a new method attached to each object. Then we could follow python rules for == and our rules for everything else, and all SAGE code would become completely unreadable (and for that matter unwriteable). So I think what you've said above is perfectly reasonable, and we just have to live with it. David --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Inconsistency in root finding
On Mar 21, 2007, at 1:37 AM, Robert Bradshaw wrote: One could also force all keys of a hashtable to live in a given ring. I don't think you'd want to do that. First, it wouldn't even solve the problem (e.g. because of the precision issues you raised before -- you can have two elements of the same ring with different precision and hence presumably different hashes, which still compare equal). Second, I can't even see technically how you would do that without modifying python in some horrible way. David --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
