Author: Russell Reagan
Date: 12:23:12 06/15/04
Go up one level in this thread
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 :)
>The intention is to do a nested iteration to find some special pairs.
>Netherlands - Germany now...
>
>Cheers,
>Gerd
>
>
>#include <stdio.h>
>#include <stdlib.h>
>#include <time.h>
>
>
>typedef unsigned __int64 BitBoard;
>
>
>class GenBitScan
>{
>public:
>
> GenBitScan(int match4nth)
> {
> clock_t start, stop;
>
> m_Lock = 0;
> m_dBCount = 0;
> m_Match4nth = match4nth;
> initPow2();
> start = clock();
> try {findDeBruijn(0, 64-6);} catch(int){}
> stop = clock();
> printf("\n// time = %.3f\n", (float)(stop - start) / CLOCKS_PER_SEC);
> }
>
>private:
> BitBoard pow2[64];
> BitBoard m_Lock;
> int m_dBCount;
> int m_Match4nth;
>
> void initPow2() {
> for (int i=0; i < 64; i++)
> pow2[i] = (BitBoard)1 << i;
> }
>
> void bitScanRoutineFound(BitBoard deBruijn)
> {
> int index[64], i;
> for (i=0; i<64; i++) // init magic array
> index[ (deBruijn<<i) >> (64-6) ] = i;
> printf("\nconst BitBoard magic = 0x%08x%08x; // the %d.\n\n",
> (int)(deBruijn>>32), (int)(deBruijn), m_dBCount);
> printf("const unsigned int magictable[64] =\n{\n");
> for (i=0; i<64; i++)
> {
> if ( (i & 7) == 0 ) printf("\n ");
> printf(" %2d,", index[i]);
> }
> printf("\n};\n\nunsigned int bitScan (BitBoard b) {\n");
> printf(" return magictable[((b&-b)*magic) >> 58];\n}\n");
> throw 0; // unwind the stack until catched
> }
>
>
> 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];
> }
> }
> }
>};
>
>
>int main(int argc, char* argv[])
>{
> if (argc < 2)
> printf("usage: genBitScan 1 .. %d\n", 1<<27);
> else
> GenBitScan(atoi(argv[1]));
> return 0;
>}
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.