Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash Collisions

Author: Robert Hyatt

Date: 18:56:06 02/22/99

Go up one level in this thread


On February 22, 1999 at 18:42:21, Don Dailey wrote:

>>>However, I don't have that many numbers (1024 you said?) as I only used 12*64
>>>since we didn't use any sort of 'boundary squares' in cray blitz.  Ditto for
>>>Crafty where I also use 12*64.  I have been meaning to go grab that table of
>>>numbers and 'steal' it for crafty, but I haven't yet, because it is in the
>>>syntax of 'fortran'.
>
>>>>I have a little piece of code I wrote that generates 64 bit random
>>>>numbers one at a time and tests each one against all the ones
>>>>previously generated.  If the new number is closer than my specified
>>>>hamming distance, I regenerate that number until it is.   To get
>>>>even 24 bit distances between any two I've had to generate almost
>>>>half a million numbers.   I have 1024 numbers in my table.
>>>>
>>>>I don't believe your random number generator is returning numbers
>>>>this good.  Maybe you can precompute them this good, I don't know.
>>>>I'm trying right now with 32 bits but it's going awfully slow.
>>>
>>>I use the Numerical Recipes RNG code.  But you are right, it won't produce
>>>such good hamming distances quickly.  I wouldn't be surprised if it takes
>>>4 billion numbers to get decent random numbers...
>
>
>Hi Bob,
>
>I just generated a 1024 entry table with hamming distances at least
>32 bits between any two.  It took about 134 million random number
>calls.
>
>>I ran some quick tests... to produce a minimum distance of 16, producing
>>768 random numbers (64 bits), takes 769 numbers from my Random64() function
>>in crafty.
>
>I get pretty much the same results.  Starting at about 15 bits, you
>start getting the occasional retry.  I think I get 1 retry with 15
>bits and maybe 2 with 16 bits.  I am of course generating a slightly
>bigger table.
>
>To go to 24 jumps this to a really big number (it took my code
>>200 million random numbers to find 768 with a hamming distance >= 24 between
>>_all_ of them.
>
>But this is not consistant with my result, getting 32 bits in less
>tries.   Are you sure it's not 200,000?    I'll recheck my code and
>make sure I'm counting right.  I haven't done much to test or debug
>the hamming code so maybe that is the problem.
>

I'm sure... 200M was the right number...  the piece of code looks like
this:



  limit=atoi(argv[1]);
  printf("hamming distance target = %d\n",limit);
  for (cur=0;cur<768;cur++) {
    printf("cycle=%d\n",cur);
    while (1) {
      ran[cur]=Random64();
      gen++;
      for (i=0;i<cur;i++)
        if (PopCnt(ran[cur]^ran[i]) < limit) break;
      if (i == cur) break;
    }
*    ran[cur+1]=~ran[cur];
*    gen++;
*    for (i=0;i<cur+1;i++)
*      if (PopCnt(ran[cur+1]^ran[i]) < limit) break;
*    if (i < cur+1) continue;
*    cur++;
  }
  printf("generated %d random numbers\n",gen);

The * lines above simply recycle the last number, by complementing it
and testing to be sure the complemented number is also acceptable.

The idea is to generate a new ran number, test it against all the previous
ones and toss it if it is not 'different enough'.

This takes over 200,000,000 numbers when limit=24...

>>One minor trick is that in general, if N is a good number, ~N is also good.
>>
>>I've been trying to find my notes on CB... but now think that maybe '32' was
>>an 'average' number rather than the abs minimum for all the numbers.
>>
>>If I had some time, I'd try to study just what the 'optimal' set would be,
>>because it must be computable...
>>
>>
>>
>>>I'll try to figure out a way to post my values here if you are interested.
>>>64 * 12 isn't horribly big, but when you display them as 64 bit values, they
>>>are big. The main issue is how to initialize such an array in a portable
>>>way...  IE (BITBOARD ran[12][64] = {{1,2,3},{4,5,6}};  The numbers 1,2,3
>>>default to 'int' which is bad.  I don't know what to do for all compilers
>>>(IE 123ULL or (BITBOARD) 123)



This page took 0.03 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.