ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

how to measure frequency of hash collisions.
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Don Dailey



Joined: 29 Apr 2008
Posts: 4323
PostPost subject: Re: how to measure frequency of hash collisions.    Posted: Sat Jun 16, 2012 10:29 pm Reply to topic Reply with quote
Don wrote:
Daniel Shawul wrote:
Don wrote:

You can estimate the collision rate by using N bits are for checking. So if your key is 64 bits, pretend it's only 60 bits and 4 bits are for collision testing. If the 4 bits do not match it was a collision. You can extrapolate to get the 64 bit collision rate estimate - each time you add a bit you can expect half the number of collisions.
Don

But that won't work because in a hash collision, the hash signature (all 64 bits) are the same for two completely different positions... You need a key from another sequence of random numbers (be it from the same or different hash function). Am I missing something ?


Yes, what you are missing is that you are not testing the 64 bit key. You are testing a 60 bit key. In my example just pretend that you are generating a 60 bit key and then a totally independent 4 bit key. Let's say for example that the you get a collision on the 60 bit key once out of 1 million matches (as judged by the 4 bit verify key.) You can expect that had this been a 64 bit key instead of 60 bits you will get only 1/16 as many collisions since 2^4 is 16. Each extra bit cuts the number of expected collisions in half.

This is superior to any of the suggested methods proposed because it does not require modification of the program in order to add more key space, you just borrow a few bits from the already existing key. So this could be added to the program with no additional overhead. In fact the program could still continue to use the full 64 bit key while doing the 60 bit key collision detection test for statistical purposes and it could even be put in the log file of the program. If you use 4 bits for collision detection then you count how many of these 60 bit keys collided and divide by 16 to get an ESTIMATE of how often a 64 bit key would have collided.


P.S. I would actually favor more than 4 bits - assuming that 60 bits does not generate very many collisions. That is because if you have to run the program for 10 minutes just to get 2 or 3 collisions you have too much noise to get a very accurate estimate. So I would experiment with the number of bits to borrow from the 64 bit key to make this produce perhaps a few dozen collisions in a minute or two. It could be a parameter. I actually don't have any clue about how many collisions a program like Komodo will produce per hour of run-time.
_________________
"Your superior intellect is no match for our puny weapons." -Kang and Kodos
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Subject Author Date/Time
how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 4:45 pm
      Re: how to measure frequency of hash collisions. Marcel van Kervinck Sat Jun 16, 2012 5:25 pm
            Some tests: Attn Don Daniel Shawul Sat Jun 16, 2012 6:25 pm
                  Re: Some tests: Attn Don Daniel Shawul Sat Jun 16, 2012 7:15 pm
      Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 9:17 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 10:05 pm
                  Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 10:23 pm
                        Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 10:29 pm
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 11:06 pm
                              Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 11:39 pm
                                    Re: how to measure frequency of hash collisions. Kevin Hearn Sat Jun 16, 2012 11:50 pm
                                          Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 12:08 am
                                          Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 12:40 am
                                    Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 11:54 pm
                                          Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 12:23 am
                                    Re: how to measure frequency of hash collisions. Marcel van Kervinck Sun Jun 17, 2012 7:55 am
                  Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 1:26 am
      Re: how to measure frequency of hash collisions. Ed Schroder Sat Jun 16, 2012 9:36 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 10:01 pm
      Re: how to measure frequency of hash collisions. H.G.Muller Sat Jun 16, 2012 10:12 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 10:31 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 2:00 am
                  Re: how to measure frequency of hash collisions. Rémi Coulom Sun Jun 17, 2012 8:30 am
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 10:49 am
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 2:58 pm
                              Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 3:41 pm
                                    Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 5:58 pm
                                          Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 9:06 pm
                                                Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 9:57 pm
      Re: how to measure frequency of hash collisions. Lucas Braesch Sun Jun 17, 2012 3:02 am
            Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 3:08 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 6:12 pm
                  Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 9:14 pm
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 10:01 pm
      Re: how to measure frequency of hash collisions. Joshua Shriver Wed Jun 20, 2012 8:45 pm
            Re: how to measure frequency of hash collisions. Ronald de Man Wed Jun 20, 2012 10:44 pm
                  Re: how to measure frequency of hash collisions. Joshua Shriver Thu Jun 21, 2012 1:51 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads