From: Robert Klemme <bob.news@...>
Date: 2005-09-17T01:11:35+09:00
Subject: Re: Sets, uniqueness not unique.

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

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

> 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).  I'll trust the Sun guys to have ensured that the
way they do it is a reasonable tradeoff between randomness and speed.

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

Kind regards

    robert