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

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.

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.

>>
>> Agreed.  Is the RCR yours?
>
> Yes.
>
>>  Maybe an RCRCR :-) is appropriate, "change
>> the hashing algorithm in that code to use LCG".
>
> Done.
>
> Thanks for the inspiring discussion!
>
>    robert

         Thank you,
         Hugh