From: Hugh Sasse <hgs@...>
Date: 2005-09-17T02:11:19+09:00
Subject: Re: Sets, uniqueness not unique.

On Sat, 17 Sep 2005, Robert Klemme wrote:

> Hugh Sasse wrote:
>> On Fri, 16 Sep 2005, Robert Klemme wrote:
>>
>>>>> That code does only one modulus on the NHASH.  Your code does it
>>>>> for each
>>>>
>>>> I wasn't following closely enough. :-)
>>>
>>> Someone talked about his brain behaving like cottage cheese today...

Looks like it still is then...
>>> :-))
>>
>> There is that. :-)
>>>
>>          [...]
>>>>>> Should that be 0x7FFF_FFFF?  (2147483647)
>>>>>> According to
>>>>>> http://www.rsok.com/~jrm/printprimes.html
>>>>>> this would seem to be a prime number, so could be used as the
>>>>>> modulus anyway.
>>>>>
>>>>> You can even use bit and on this which I would expect to be
>>>>> slightly more efficient.
>>
>> I thought about this over lunch.  I don't think you can use bit AND.
>>
>> Suppose we have a 4 bit machine[!] and MAX_HASH is 3
>>
>>    6 % 3 == 0, but 6 & 3 == 2
>>    7 % 3 == 1, but 7 & 3 == 3
>
> Erm, if you want to use bit AND instead of modulo you have to use
> different values (i.e. the modulo value us bit and value + 1):
>
>>> 8.times {|i| print i % 4, " ", i & 3, "\n"}
> 0 0
> 1 1
> 2 2
> 3 3
> 0 0
> 1 1
> 2 2
> 3 3

When I did that in my head I munged it then! (hence my comment
above).
>
> This in turn means that the modulo always must be a power of two and thus
> is extremely unlikely to be prime.  I would even go so far as to claim
> that the likelyhood is smaller than every nonzero positive epsilon in the
> real numbers that you can think of.  :-)

But in this case (2 ** n) - 1 is prime, which is what we want.  So I
think it should be 0x8000_0000 (2147483648) for the & version,
equivalent to 0x7FFF_FFFF for the % version.

>
>> etc.  The theory behind linear *congruential* random number
>> generators, (which is how we're stirring the hashes) is based on
>> primality in modulo arithmetic.  I think if we destroy that
>> relationship things will be less random and we'll get more
>> collisions.
>
> Well, sometimes you'll have to do tradeoffs.  The Java implementation
> doesn't even use and or modulo to limit the value (not needed with Java
> int, they simply wrap).

Ouch.

> I'll trust the Sun guys to have ensured that the
> way they do it is a reasonable tradeoff between randomness and speed.

Java was intended for small systems originally, then backwards
compatibility, ....
>
>> Testing for randomness is tricky enough, so I'd not like to have to
>> prove this. But I have a suspicion that given the amount of work by
>> Knuth and others on the topic, if & could be used instead of % it
>> would be the recommended way to do it, because it is cheaper/faster.
>
> Yes, if you want to use a prime you definitely have to use modulo (see
> above).  I was more on the Sun side, i.e. just limiting the value in order
> to keep it a Fixnum.

I suppose I may be aiming too much for perfection, but I wonder how
the & 0x8000_0000 version stacks up.
>
> Kind regards
>
>    robert
>
>
>