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