Author: Heiner Marxen
Date: 13:03:31 09/24/01
Go up one level in this thread
On September 24, 2001 at 15:41:07, Antonio Dieguez wrote: >On September 24, 2001 at 15:27:35, Robert Hyatt wrote: > >>On September 24, 2001 at 13:53:58, Antonio Dieguez wrote: >> >>> >>>Also another stupid question, in another post I see calculated the index for >>>hashtable with HV%N, with N the capacity, in that case is it a bit safer to not >>>use an N=2^something? or it is almost the same or there are drawbacks, or I'm >>>not understanding other thing? >> >>If you use %, then you can use any size hash table you want. I don't use % >>because it generally requires two registers, one for the quotient, one for >>the remainder. Not to mention integer divide has always been a pretty slow >>operation. With a perfect power of 2, you can use & (2^N - 1) for the >>address extraction... with a single-cycle instruction penalty. > >sure, but would be interesting to know if using an N!=2^m fixes a bit the >decreasing security of the hash. I don't have clear how much, that is why I >asked. That depends on the quality of your hash value HV. If it is a very good one, using any m bits of HV would yield a nearly optimal (equal) distribution. If your hashing algorithm is not very good, then selecting m bits from it may yield a not so good distribution, what causes only part of the hash table to be really used. In that case, a prime N can help a lot. Zobrist hashes with carefully selected random values is good enough to just select some m bits without noticable problems. 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.