Author: Dieter Buerssner
Date: 12:34:18 08/27/03
Go up one level in this thread
On August 26, 2003 at 21:14:40, Ricardo Gibert wrote: >What I meant was the modulo method applied to the 64 bit hash key rather than >the truncated hash key. Then you are of course right, sorry. I mentioned, that it is a bit tailored for 32 bit systems (where you will have always less than 2^^32/12 entries). Under these conditions, I see no problem for the multiplication. One could even use something like 64-bit*32-bit -> 96 bit multiplication, which would use at most 3 mul instructions (I think, one could even ignore some carries) to get the upper bit results. Probably still significantly less effort, than doing a real 64-bit/32-bit modulo. And on 64 bit machines, there might be 64-bit*64-bit -> 128 bit multiplications. Or one could do the multiplication in floating point (IEEE double precision floating point would be enough for up to 2^^53 HT entries - probably more than enough for my entire life ...). On current x86 systems the rounding to int is not very efficient, however. >The multiplication method won't allow you to use the full 64 bits. But that is not a real problem. You want rather uniformly distributed indices. How many bits are used for this task, is not really important. One could even see it as an advantage. Say you have a n-bit hash-key. You use the upper m bits for index calculation, and can store the lower n-m bits in the HT for further verification of the equalness of the position. With % (unless power of 2) this would not be possible. >You have to >throw away enough bits to accommodate the result after the multiplication. Which, as I tried to explain above, I see not as a problem. If we assume, that you start with slightly decent random numbers. Combining such numbers with XOR (or add or sub or ...) cannot make worse looking random numbers. Cheers, Dieter
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.