Author: Ricardo Gibert
Date: 14:28:23 08/27/03
Go up one level in this thread
On August 27, 2003 at 15:34:18, Dieter Buerssner wrote: >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. This last remark about % is interesting. I hadn't thought about verification if the modulo method is used. I suppose you can use a 2nd modulus that is relatively prime to 1st. Or even better is to use the value of the quotient. In any case, the modulo method is the slow way, so it doesn't really matter computer chess-wise. > >>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.