Author: Uri Blass
Date: 13:51:47 11/08/02
Go up one level in this thread
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
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.