Hi Robert, hi Stefan, On 2013-08-28, Robert Bradshaw <rober...@math.washington.edu> wrote: > What could perhaps be added is some kind of a normalization routine > (to be implemented by subclasses) that is called before performing a > hash. This might be quite expensive.
Sorry, I intended to answer yesterday evening along the same lines, but my internet connection broke. I think we should look at how equality of fraction field elements is defined, and what we can learn from it for the hash function. By definition, n1/d1 is equal to n2/d2 if and only if n1*d2==n2*d1. But because of mixing terms from right and left, this is not useful for the hash, because the hash only knows about *one* element. But there is also a generically implemented method .reduce() for fraction field elements (so, not necessarily needed to implement it in subclasses). Of course, it is expensive and it may fail (if the gcd is not defined). But *if* it works, then fraction f1 is equal to fraction f2 if and only if numerator and denominator of f1.reduce() are equal to those of f2.reduce(). Hence, this is the right thing to do for the hash: Just insert self.reduce() at the beginning of self.__hash__(). I'd rather have a slow hash than a totally broken hash. One point needs to be fixed, though. self.reduce() would do the same expensive computations even if self already *is* reduced. Hence, .reduce() should do some caching. And if self.reduce() fails, then I think self should not be hashable! > There's also some fuzziness about > what equality should be used, e.g. is this OK? > > sage: S = set([(x+1)^2]) > sage: x^2 + 2*x + 1 in S > False This is OK, because (x+1)^2 and x^2+2*x+1 do not compare equal, in terms of cmp: sage: cmp((x+1)^2, x^2 + 2*x + 1) 1 If I am not mistaken, containment in sets and dicts relies on cmp and not on ==. Hence, in this case, I think the hash is not to blame. Best regards, Simon -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/groups/opt_out.
