Author: Heiner Marxen
Date: 17:19:17 02/18/02
Go up one level in this thread
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: [snipped] 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. 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 :-) Cheers, Heiner
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.