Author: Gerd Isenberg
Date: 11:50:46 06/15/04
Go up one level in this thread
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?
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.