2014-05-20 8:17 GMT+02:00 phil@highoctane.be <phil@highoctane.be>:
On Tue, May 20, 2014 at 7:28 AM, Sven Van Caekenberghe <sven@stfx.eu>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 <sean@clipperadams.com> 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.