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.