Wiki

User Tools

Site Tools

Trace:
chess:programming:de_bruijn_sequence:using_a_de_bruijn_sequence

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
chess:programming:de_bruijn_sequence:using_a_de_bruijn_sequence [2021/10/28 14:55] – created peterchess:programming:de_bruijn_sequence:using_a_de_bruijn_sequence [2021/10/29 00:05] (current) – [Chess - Programming - de Bruijn Sequence - Using a De Bruijn Sequence] peter
Line 1: Line 1:
 ====== Chess - Programming - de Bruijn Sequence - Using a De Bruijn Sequence ====== ====== Chess - Programming - de Bruijn Sequence - Using a De Bruijn Sequence ======
 +
 +Here is a pre-calculatedde Bruijn Sequence.
 +
 +<code cpp>
 +int MultiplyDeBruijnBitPositions[64]
 +{
 +  0,1,2,4,8,17,34,5,11,23,47,31,63,62,61,59,
 +  55,46,29,58,53,43,22,44,24,49,35,7,15,30,60,57,
 +  51,38,12,25,50,36,9,18,37,10,21,42,20,41,19,39,
 +  14,28,56,48,33,3,6,13,27,54,45,26,52,40,16,32
 +};
 +
 +int getLog2_DeBruijn(ulong v)
 +{
 +  return MultiplyDeBruijnBitPosition[(ulong)(v * 0x022fdd63cc95386dull) >> 58];
 +}
 +</code>
 +
 +<WRAP info>
 +**NOTE:**  The conventional power of 2 and square is extremely slow. (100M calculations needs hours).
 +
 +  *  There are many alternative methods to make this faster, including:
 +      * **SIMD and SWAR Techniques**:
 +      * **De_Bruijn Splited 32bits**:
 +      * **De_Bruijn 64bits version**:
 +      * **De_Bruijn 128bits version**:
 +
 +  * The **De_Bruijn 128bits** version is the fastest.
 +
 +</WRAP>
 +
 +----
 +
 +===== Power of 2 using SIMD and SWAR Techniques =====
 +
 +<code cpp>
 +ulong NumBits64(ulong x)
 +{
 +    return (Ones64(Msb64(x) - 1ul) + 1ul);
 +}
 +
 +ulong Msb64(ulong x)
 +{  
 +    //http://aggregate.org/MAGIC/
 +    x |= (x >> 1);
 +    x |= (x >> 2);
 +    x |= (x >> 4);
 +    x |= (x >> 8);
 +    x |= (x >> 16);
 +    x |= (x >> 32);
 +    return(x & ~(x >> 1));
 +}
 +
 +ulong Ones64(ulong x)
 +{
 +    //https://chessprogramming.wikispaces.com/SIMD+and+SWAR+Techniques
 +    const ulong k1 = 0x5555555555555555ul;
 +    const ulong k2 = 0x3333333333333333ul;
 +    const ulong k4 = 0x0f0f0f0f0f0f0f0ful;
 +    x = x - ((x >> 1) & k1);
 +    x = (x & k2) + ((x >> 2) & k2);
 +    x = (x + (x >> 4)) & k4;
 +    x = (x * 0x0101010101010101ul) >> 56;
 +    return x;
 +}
 +</code> 
 +
 +----
 +
 +===== Power of 2 using De_Bruijn Splited 32bits =====
 +
 +<code cpp>
 +int NumBits64(ulong val)
 +{
 +    if (val > 0x00000000FFFFFFFFul)
 +    {
 +        // Value is greater than largest 32 bit number,
 +        // so calculate the number of bits in the top half
 +        // and add 32.
 +        return 32 + GetLog2_DeBruijn((int)(val >> 32));
 +    }
 +    // Number is no more than 32 bits,
 +    // so calculate number of bits in the bottom half.
 +    return GetLog2_DeBruijn((int)(val & 0xFFFFFFFF));
 +}
 +
 +int GetLog2_DeBruijn(int val)
 +{
 +    uint32 v = (uint32)val;
 +    int r;      // result goes here
 +
 +    static const int MultiplyDeBruijnBitPosition[32] = 
 +    {
 +        0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
 +        8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
 +    };
 +
 +    v |= v >> 1; // first round down to one less than a power of 2 
 +    v |= v >> 2;
 +    v |= v >> 4;
 +    v |= v >> 8;
 +    v |= v >> 16;
 +
 +    r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
 +    return r;
 +}
 +</code>
 +
 +----
 +
 +===== Power of 2 using De_Bruijn 64bits version =====
 +
 +<code cpp>
 +static readonly int[] bitPatternToLog2 = new int[64] { 
 +    0, // change to 1 if you want bitSize(0) = 1
 +    1,  2, 53,  3,  7, 54, 27, 4, 38, 41,  8, 34, 55, 48, 28,
 +    62,  5, 39, 46, 44, 42, 22,  9, 24, 35, 59, 56, 49, 18, 29, 11,
 +    63, 52,  6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
 +    51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
 +}; // table taken from http://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator
 +static readonly ulong multiplicator = 0x022fdd63cc95386dUL;
 +
 +public static int bitSize(ulong v) {
 +    v |= v >> 1;
 +    v |= v >> 2;
 +    v |= v >> 4;
 +    v |= v >> 8;
 +    v |= v >> 16;
 +    v |= v >> 32;
 +    // at this point you could also use popcount to find the number of set bits.
 +    // That might well be faster than a lookup table because you prevent a 
 +    // potential cache miss
 +    if (v == (ulong)-1) return 64;
 +    v++;
 +    return MultiplyDeBruijnBitPosition2[(ulong)(v * multiplicator) >> 58];
 +}
 +</code>
 +
 +----
 +
 +===== Power of 2 using De_Bruijn 128bits version =====
 +
 +<code cpp>
 +static readonly int[] bitPatternToLog2 = new int[64] { 
 +    0, // change to 1 if you want bitSize(0) = 1
 +    1,  2, 53,  3,  7, 54, 27, 4, 38, 41,  8, 34, 55, 48, 28,
 +    62,  5, 39, 46, 44, 42, 22,  9, 24, 35, 59, 56, 49, 18, 29, 11,
 +    63, 52,  6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
 +    51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
 +}; // table taken from http://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator
 +static readonly ulong multiplicator = 0x022fdd63cc95386dUL;
 +
 +public static int bitSize(ulong v) {
 +    v |= v >> 1;
 +    v |= v >> 2;
 +    v |= v >> 4;
 +    v |= v >> 8;
 +    v |= v >> 16;
 +    v |= v >> 32;
 +    // at this point you could also use popcount to find the number of set bits.
 +    // That might well be faster than a lookup table because you prevent a 
 +    // potential cache miss
 +    if (v == (ulong)-1) return 64;
 +    v++;
 +    return MultiplyDeBruijnBitPosition2[(ulong)(v * multiplicator) >> 58];
 +}
 +</code>
 +
 +----
 +
 +===== References =====
 +
 +https://stackoverflow.com/a/21888833/1240074
 +
 +https://stackoverflow.com/a/21889329/1240074
 +
 +https://stackoverflow.com/a/21888542/1240074
 +
  
chess/programming/de_bruijn_sequence/using_a_de_bruijn_sequence.1635432957.txt.gz · Last modified: 2021/10/28 14:55 by peter
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki