2014-05-20 8:17 GMT+02:00 [email protected] <[email protected]>: > On Tue, May 20, 2014 at 7:28 AM, Sven Van Caekenberghe <[email protected]>wrote: > >> So ? >> >> 1/2 hash ~= 0.5 hash >> > > ((1/2) hash = 0.5 hash) true > ((1/2) hash ~= 0.5 hash) true > > and > > ((1/3) hash =(1.0/3) hash) false > > The implementation (in 3.0) has a special case for denominator is a power > of 2: > > Fraction>>hash > "Hash is reimplemented because = is implemented. > Care is taken that a Fraction equal to a Float also have an equal hash" > > | tmp | > denominator isPowerOfTwo ifTrue: [ > "If denominator is a power of two, I can be exactly equal to a Float" > tmp := self asFloat. > tmp isFinite ifTrue: [^tmp hash]]. > "Else, I cannot be exactly equal to a Float, use own hash algorithm. > (Assume the fraction is already reduced)" > ^numerator hash bitXor: denominator hash > > > Float>>hash > "Hash is reimplemented because = is implemented. Both words of the float > are used; 8 bits are removed from each end to clear most of the exponent > regardless of the byte ordering. (The bitAnd:'s ensure that the > intermediate results do not become a large integer.) Slower than the > original version in the ratios 12:5 to 2:1 depending on values. (DNS, 11 > May, 1997)" > > (self isFinite and: [self fractionPart = 0.0]) ifTrue: [^self truncated > hash]. > ^ (((self basicAt: 1) bitAnd: 16r00FFFF00) + > ((self basicAt: 2) bitAnd: 16r00FFFF00)) bitShift: -8 > > > Mmmh, I am curious to know what the rationale for this is. > > A Float exact representation is of the form
(-1 raisedTo: signBit) * integerSignificand * (2 raisedTo: biasedExponent). Thus it is either an Integer, or a Fraction whose denominator is a power of 2 (when biasedExponent < 0). In Squeak and Pharo, Float equality versus other numbers is based on equality of exact representation. I think this has been changed too in Dolphin and gst, but not in VW. So a naive implementation of hash matching those equality rules could be Float>>hash ^self asTrueFraction hash But we try to avoid sending asTrueFraction because it costs (involves LargeInt arithmetic), so the logic for hash is: if Float can be an integer, convert it to integer. if Fraction could be a Float, convert it to Float. Note that we could also check the other requirement (Fraction numerator highBitOfMagnitude <= Float precision). Also note that ^ (((self basicAt: 1) bitAnd: 16r00FFFF00) + ((self basicAt: 2) bitAnd: 16r00FFFF00)) bitShift: -8 is the historical Squeak hash method for Float and is really POOR (many collisions, only half bits are used !!!) I think I changed it in Squeak, but can't remember. > Getting into: > > Fraction>>isPowerOfTwo > |reduced| > reduced := self reduced. > ^(reduced numerator = 1 and: [reduced denominator isPowerOfTwo]) > or: [reduced denominator = 1 and: [reduced numerator isPowerOfTwo]] > > calls in >>reduced, which in turn calls gcd: ... > > That's quite something to be aware of. > > I don't see no need for reduced here. All Fraction are (should be) reduced. replaced reduced by self, and you won't get any gcd: > Phil > > >> >> I mean what would you expect, how should this have to work ? >> >> Maybe the hashing specialists have something to say about this. >> >> On 20 May 2014, at 01:38, Sean P. DeNigris <[email protected]> wrote: >> >> > (1/2) teaspoons hash ~= 0.5 teaspoons hash >> > >> > b.t.w. Phexample caught this automatically because it checks hashes when >> > comparing for equality... pretty cool >> > >> > >> > >> > ----- >> > Cheers, >> > Sean >> > -- >> > View this message in context: >> http://forum.world.st/Aconcagua-Hashing-Bug-tp4759622.html >> > Sent from the Pharo Smalltalk Developers mailing list archive at >> Nabble.com. >> > >> >> >> >
