Computer Chess Club Archives




Subject: Re: Non power of two hash table sizes

Author: Dann Corbit

Date: 17:34:09 02/18/02

Go up one level in this thread

On February 18, 2002 at 20:19:17, Heiner Marxen wrote:
>On February 18, 2002 at 18:58:54, Dann Corbit wrote:
>>On February 18, 2002 at 17:37:27, Heiner Marxen wrote:
>>>On February 18, 2002 at 17:07:11, Dann Corbit wrote:
>>>>On February 18, 2002 at 16:56:37, Benny Antonsson wrote:
>>>>>Why must it be a prime number ?
>>>>When a composite number is chosen, factors in the number can cause a bad
>>>>[non-uniform] distribution.
>>>>See Knuth's "The Art of Computer Programming", Volume 3 'Sorting and Searching'
>>>>page 516 for a detailed explanation.
>>>IMO this is only an issue if you start with a non-uniform distribution.
>>>If your hash key is already very good (Zobrist should be good enough),
>>>you may take any hash table size and do
>>>   hash_index = hash_key % hash_table_size;
>>>(After all, taking the low N bits is just an efficient way to do key % (1<<N))
>>>In doubt (probably anyhow) just measure the quality of the distribution.
>>>It is of high quality, it behaves similar to a true random distribution.
>>>Many years ago I've done such experiments, but I do not remember the details
>>>any more, sorry.
>>It's probably not much of a worry if you have really good random number
>>generators and use a sophisticated hash.  It should be noted (however) that many
>>C distributions have a particulary onerous rand() function (and the one in the
>>POSIX documentation is just plain *bad*).  From the C FAQ:
>Yes, I know that rand() is really bad.  One may use it to generate a tempfile
>name, or an IPC key, but not much more.  In BSD-ish systems there is random(),
>on System5 one may have rand48(), but if you want to be portable, just roll
>your own copy of e.g. the Mersenne Twister.  _That_ one should be good enough.
>Under Linux you find even devices /dev/random and /dev/urandom, which provide
>_real_ random numbers.

So did the Commodore 64.  You just cranked up the white noise generator and then
read the sound port.

Of course, if they are _really_ random, eventually, you will get a trillion
zero's in a row.

>Or... pick your favorite disk partition, feed it to some compressor, and fold
>the result with XOR down to the wanted size.  Also some sort of random number.
>(Yes, I have done that once :-)

I've never built an "entropy vice" like that.  I certainly hope that I never
have to.

This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.