Author: Ron Murawski
Date: 15:29:23 11/08/02
Go up one level in this thread
On November 08, 2002 at 16:51:47, Uri Blass wrote: >On November 08, 2002 at 16:04:19, Ingo Lindam wrote: > >>On November 08, 2002 at 12:50:41, J. Wesley Cleveland wrote: >> >>>On November 08, 2002 at 10:50:34, Ron Murawski wrote: >>> >>>[snip] >>>> >>>>I'm investigating power-of-two size vs prime size using single-probes. It's not >>>>at all apparent to me whether the smaller table used for a power-of-two size >>>>might slow down the engine more than the expensive mod instruction on a larger >>>>table would. In other words, if there are 36K slots available, power-of-two >>>>would only use 32K slots, whereas the prime size would use almost all of the >>>>36K. >>> >>>You can use multiply instead of mod, e.g. with 32 bit keys: >>> >>>table_index = (key*number_of_table_slots) >> 32; >> >>When you are hashing you want first of all minimize the situations where you get >>the same hashing index for two different keys. Therefore a prime numer is >>definitly the best. So from this point of view obtaining >> >>table index = key MODULO p, p is prime number should be optimal > > >Can you explain why? > >1/p when p is prime is not smaller than 1/p when p is not prime. > >If you say that the probability to get hash collision is not always 1/p then >explain why. > >It is 1/p when the numbers are real random numbers. > >Uri "when the numbers are real random numbers" That's the problem Uri, these numbers aren't "real" random numbers, they are pseudo-random and follow a repeatable sequence. So let's say you have a great 64-bit pseudo-random number generator (prng). But you are only going to use a subset of those bits in order to determine random slots. Can you state with any certainty that your great prng won't have bad behavior or repeating patterns using the subset of bits that you happen to pick? By observation and testing I have found that slot counts near a power-of-two seem to play more strongly than those that are midway between. I too, would be interested if anyone could contribute some theory to this duscussion. Ron
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.