It should be noted that hashing should ideally be a very quick operation. Also, it's not possible to have x == y => hash(x) == hash (y) for a useful hash function. (For example, the equalities z == mod (z, 2) and z == mod(z, 3) would force hash() to be constant on the integers.) I think the goal is to make a hash function that is fast but within reason respects any obvious, natural inclusions (e.g. given K/F, it shouldn't be hard to make hash(K(a)) = hash(a) for a in F).
- Robert On Mar 21, 2007, at 1:09 AM, Nick Alexander wrote: > So I've read this thread twice, and I can't understand what should > happen next. Can someone sketch how algebraic extensions (say L/K/Q) > should hash? I suggest: > > Q.__hash__ tries to __call__ to Z, and if that fails, hashes how it > does now. > > K.__hash__ tries to __call__ to Q, and if that fails, hashes based on > coefficients. > > L.__hash__ tries to __call__ to K, and if that fails, hashes based on > coefficients OVER Q. > > That does what I think is the right thing. But what if we have L1,L2/ > K2/K1/Q, but L1 and L2 are extensions of K1 (so they don't know about > K2). Then an element of L1 that's really in K2 and the same element > of L2 that's really in K2 are supposed to hash the same? > > Aside 1: none of the canonical coercions are in place yet, AFAICT. > Aside 2: maybe these issues are easier over GF(p^k), since there is a > standard choice for field representation? > > It's making my head spin. > Nick > > On Mar 20, 11:09 pm, David Harvey <[EMAIL PROTECTED]> wrote: >> 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/ -~----------~----~----~----~------~----~------~--~---
