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.
>