Author: Gerd Isenberg
Date: 22:47:18 02/28/06
Go up one level in this thread
On March 01, 2006 at 01:16:38, Gerd Isenberg wrote:
>On February 28, 2006 at 17:51:34, Randall Shane wrote:
>
>>Gerd,
>>
>>Since the DeBruijn approach looks interesting to me, I thought I'd give it a
>>try.
>>
>>I tried running the code given 2 messages above for the optimized De Bruijn
>>generator, with the following derived class and main function :
>>
>>
>>class DBG : public DeBruijnGenerator
>>{
>>public:
>> DBG() {}
>>
>> void deBruijnFound(BitBoard deBruijn) const
>> {
>> printf("%-9d : %016I64X\n", count+1, deBruijn);
>> // Running with the Microsoft compiler on a Pentium IV machine
>> }
>>};
>>
>>void main(int argc, char* argv[])
>>{
>> DBG *dbg = new DBG();
>> dbg->genDeBruijn(3);
>> fflush(stdout);
>>}
>>
>>just to check it out. I have it generating De Bruijn sequences of length 8 (all
>>patterns of 3 bits).
>>
>>I get the results :
>>
>>1 : 0000000000000017
>>2 : 000000000000003D
>>
>>The second one appears to be in error -- it should be hex 1D (00011101).
>>
>>I'd try one of the earlier generators, but I can't find them :-(.
>>
>>Anyway, though you'd like to know..
>
>Thanks - may be introduced by the depth-2 optimization...
>Indeed with some additional cost the if "(depth>2)" case may be skipped.
>Will have a closer look...
why not keep it simple :-)
void __fastcall searchDeBruijn(unsigned int i) {
if ( depth > 1 ) {
unsigned int j = (i+i)&mask; // next even index
lck ^= pow2[i]; // lock current index
depth--; // sequence index _East_One
if ( (lck & pow2[j]) == 0 ) { // next even index unlocked?
seq &= ~pow2[depth]; // "append" zero
searchDeBruijn(j); // do recursive search with next even index
}
if ( (lck & pow2[j+1]) == 0 ) { // next odd index unlocked?
seq |= pow2[depth]; // "append" one
searchDeBruijn(j+1); // do recursive search with next odd index
}
depth++; // sequence index _West_One
lck ^= pow2[i]; // unlock current index
} else if ( (lck & pow2[(i+i+1)&mask]) == 0 ) {
deBruijnFound(seq); // bit zero was already set during initialization
count++;
}
}
0x0000000000000017
0x000000000000001d
This page took 0.01 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.