Author: Sune Fischer
Date: 15:42:08 04/07/04
Go up one level in this thread
On April 07, 2004 at 18:10:09, Dieter Buerssner wrote: >On April 07, 2004 at 11:59:58, Sune Fischer wrote: > >>>>It is quite similar from the point on where the hash table is full. >>> >>>absolutely not! >>>the probability that *any* two 64-bit signatures are the same goes from 0...1 as >>>you increase table size and is about 0.5 at 2^32 entries (and goes to 1 very >>>rapidly from there). >> >>I suspect you may in the heat of the moment have thought >>that 2^32 is half of 2^64? >> >>It is not of course :) > >I think, Martin is correct. This does not mean, that you will have many >collisions. It means, that each 2^33 probes, you will have one collision. This fits pretty good with the square root of the birthday problem, of course in our case we usually don't have 2^32 has entries so our collision rate will be much lower. Also in the birthday problem the probabilities start out low because there is not much to collide with. The analogy must break down when the hash table starts to get full as replacements begin to "remove pupils from the class". The birthday model doesn't account for that. I just always assume a full hash table because the calculation is even easier in that case. -S. >Regards, >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.