Author: Ingo Lindam
Date: 13:04:19 11/08/02
Go up one level in this thread
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 The second aspect is that a table with 2^n entries make much more sense than a table with 2^n+1 entries. But 2^n-1 might be far away from the properties you like at the prime numbers. So 2^32-1 = 4294967295 I don't like that much, because with k = 3,5,15,... 2^32 MODULO k != 0 for to many 'k's It may be a good comprimise to use 2^n-1 with n being a prime number... because than 2^n-1 is a prima number, too AND has 2^n-1 property as well. Ofcause 2^n-1 with n being a prime number will not have the propertie 2^n-1 = 2^(2^n)-1 that you also seem to like. Best regards, Ingo
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.