Author: Gerd Isenberg
Date: 14:43:10 06/15/04
Go up one level in this thread
On June 15, 2004 at 15:23:12, Russell Reagan wrote:
>On June 15, 2004 at 14:50:46, Gerd Isenberg wrote:
>
>>Slight improvement of the recursive de Bruijn generator.
>>Precalculated power of two and try catch block...
>>Takes under three minutes now on my Athlon-XP2.8:
>>
>>C:\Source\genBitScan\Release>genbitscan 134217727
>>
>>const BitBoard magic = 0x03f79d71b4cb0a89; // the 134217727.
>>
>>const unsigned int magictable[64] =
>>{
>>
>> 0, 1, 48, 2, 57, 49, 28, 3,
>> 61, 58, 50, 42, 38, 29, 17, 4,
>> 62, 55, 59, 36, 53, 51, 43, 22,
>> 45, 39, 33, 30, 24, 18, 12, 5,
>> 63, 47, 56, 27, 60, 41, 37, 16,
>> 54, 35, 52, 21, 44, 32, 23, 11,
>> 46, 26, 40, 15, 34, 20, 31, 10,
>> 25, 14, 19, 9, 13, 8, 7, 6,
>>};
>>
>>unsigned int bitScan (BitBoard b) {
>> return magictable[((b&-b)*magic) >> 58];
>>}
>>
>>// time = 162.263
>>
>>
>>Anyway, i have the dumb feeling that there is a smarter and much faster way, to
>>generate or count 2**26 (*2) 64-bit de Bruijn sequences.
>>Anybody has a clue here about a smarter algorithm or about a forum?
>
>
>Hi Gerd,
>
>Is it true that every de Bruijn sequence contains the same number of 1-bits? For
>example, 00011101 and 00010111 both contain four 1-bits. Do all de Bruijn
>sequences of length 8 contain four 1-bits? If this is the case, then you can
>jump to the next highest number with the same number of one bits using this
>function:
>
>// Next higher number with same number of 1-bits
>// Taken from the book, "Hacker's Delight" by Henry S. Warren Jr.
>
>unsigned snoob (unsigned x) {
> unsigned smallest, ripple, ones;
>
> smallest = x & -x;
> ripple = x + smallest;
> ones = x ^ ripple;
> ones = (ones >> 2) / smallest;
> return ripple | ones;
>}
>
>Would this help, or not? Anyway, I haven't had a chance to see how your code
>works. I will look at it and think about it. Thanks for posting. I always enjoy
>these bit-twiddling discussions :)
>
>
Thanks,
yes, there are always 32 ones and zeros, but the derivation varies in 2**26
ways. Six leading zeros, the first 6-bit sequence, index 0.
The final bit 2**0, must always be set, because of the five trailing zeros
(if bit 0 is shifted to bit 63 later in the bitscan, those trailing zeros become
real ;-)
Therefore the last index is always 32 and should not occur before (left) in the
sequence.
The snoop-fuction is fine and really interesting, but i doubt it is usefull
here. It is unclear how many interlaced 6-bitsub-sequences got changed and how
the m_Lock bookholding should be kept consistent.
And {32 over 64} seems a big larger than 2**26 ;-)
I'm thinking about shuffling some sequences around, if the first one is found.
I gave some further comments on that recursive routine:
Starting with "depth" 57, leaving bits 63,62,61,60,59,58, the first six bits
always zero. And now the algorithm recursively alternates a bit at position
"depth" with decreasing depth from right to left.
First try is "0", second "1", both during the recursive calls of that function.
Lock is initialized with zero and "unique", the first index is zero too.
The index is determined by shifting "depth" bits left and masking with 63.
At "interior" nodes > 0, the index is tagged in the 64-bit m_Lock word and may
therefore not occur twice due to the initial if-statement in deeper recursions.
So after index 0 is tagged, and trying to concat the first binary "0", it
immediatly fails next depth due to the index is already reserved by the more
left 6-bit sub-sequence.
The ( ...&& unique != 64/2 ) is for performance only, because 32 must be the
last index and if it occurs before, we can already stop going deeper to bit 0.
At depth one there is only one alternative to set a "one" at bitposition zero.
If, without a lock due to a duplicate index, a terminal node at depth zero is
reached, a de Bruijn sequence is found and some funny routines may called with
it.
Until now 58 bits in m_Lock are already set, 6 bits are still zero, the
remaining six sequences from the current from depth 0, the bits {5..0} until
bits {0..-5} = 100000B = 32.
Due to the "nature" of de Bruin sequences there is no need to check the final
five resp. four indicies (the last, 32 is already checked).
I did it, they simply fit.
void findDeBruijn(BitBoard seq, int depth)
{
int unique = (int) (seq>>depth) & (64-1);
if ( (m_Lock & pow2[unique]) == 0 && unique != 64/2 )
{
if ( depth == 0 )
{
if ( ++m_dBCount == m_Match4nth )
bitScanRoutineFound(seq);
if ( ++m_dBCount == m_Match4nth )
bitScanRoutineFound(2*seq);
}
else
{
m_Lock ^= pow2[unique];
if ( depth > 1 )
findDeBruijn(seq, depth-1);
findDeBruijn(seq | pow2[depth-1], depth-1);
m_Lock ^= pow2[unique];
}
}
}
The found "real" and odd de Bruijns may be shifted by one left to get an even
Sequence with a similar look up array - each index is decremented by one modulus
64.
Cheers,
Gerd
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.