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 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.