Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Chess - Programming - de Bruijn Sequence ======

A **de Bruijn Sequence** represents all possible sequences of a given length in a way that is as __compressed__ as possible.

It can be used to build a private **bitScanForward** routine, and to get the LSB (Least Significant Bit).

A chess board is conveniently 8 x 8 squares, and these can be represented by the numbers 0-63, which is a nice fit for a six-bit long De Bruijn sequence.

  * 64-bit De Bruijn Sequences are 64(+5 wrapped)-bit strings, containing 64 overlapping unique sub-strings (ld(64)==6-bits).
  * Because multiplying a De Bruijn Sequence with a single bit or power of two value acts like a shift left, this multiply with extracting the upper six bits by shift right 64-6=58 is a well known bitscan-approach to determine the index/position of a single isolated one in a 64-bit word.
  * The are 67,108,864 == 0x4000000 == 2^26 Sequences with start index 0 and therefore last index 32 (last index requires wrap of the 5 upper bits, which are all zero).
    * There are 64 times more sequences by rotating the initial one.
    * So in total 2^32 possible 64*6bit De Bruijn Sequences!

----

===== De Bruijn for B(2,4) =====

The cyclic sequence **0000100110101111** of length 16 is a de Bruijn sequence for n = 4.

The 16 unique sub-strings of length 4 when considered cyclicly are:

<code>
0000,0001,0010,0100,1001,0011,0110,1101,1010,0101,1011,0111,1111,1110,1100,1000
</code>

----

Taking each 4-bits

<code>
0000100110101111
</code>

returns:

<code>
0000
 0001
  0010
   0100
    1001
     0011
      0110
       1101
        1010
         0101
          1011
           0111
            1111
             1110
</code>

<WRAP info>
**NOTE:** The last 3 wraps around to the start to get the 4th digit.
</WRAP>

----

===== de Bruijn values =====

^n^de Bruijn^
|1|01|
|2|1100|
|3|00010111|
|3|01110100|
|4|0000100110101111|
|4|1111011001010000|
|5|11010100111011000101111100100000|
|6|0000001000011000101001111010001110010010110111011001101010111111|

----

[[Chess:Programming:de Bruijn Sequence:About De Bruijn Sequences|About De Bruijn Sequences]]

[[Chess:Programming:de Bruijn Sequence:De Bruijn Sequence Generator|De Bruijn Sequence Generator]]

[[Chess:Programming:de Bruijn Sequence:De Bruijn Sequence on a Chess Board|De Bruijn Sequence on a Chess Board]]

[[Chess:Programming:de Bruijn Sequence:Get De Bruijn Sequence|Get De Bruijn Sequence]]

[[Chess:Programming:de Bruijn Sequence:Using a De Bruijn Sequence|Using a De Bruijn Sequence]]

[[Chess:Programming:de Bruijn Sequence:8-bit Example|8-bit Example]]

----

TODO

<code>
Why does the standard numbering equation for de Bruijn sequences give differing results for dB(16,4) and dB(2,16), when both are 16 bits?
De Bruijn sequences are numbered by the equation
dB(k,n) = ((k!)^(k^(n-1)))/(k^n).
When we have dB(2,16), the computed value is of the order 2.1598E+9859 .
For dB(16,4), the computed value is of the order 2.7629E+54556.
Yet, both sequences are represented within just 64K bytes of memory.
Only one of these computations can be correct.
</code>

----


===== References =====

https://en.wikipedia.org/wiki/De_Bruijn_sequence

https://www.chessprogramming.org/De_Bruijn_Sequence

http://supertech.csail.mit.edu/papers/debruijn.pdf

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1038.9096&rep=rep1&type=pdf

https://stackoverflow.com/questions/37083402/fastest-way-to-get-last-significant-bit-position-in-a-ulong-c

https://cstheory.stackexchange.com/questions/19524/using-the-de-bruijn-sequence-to-find-the-lceil-log-2-v-rceil-of-an-integer

https://docplayer.net/167480236-Using-de-bruijn-sequences-to-index-a-1-in-a-computer-word-charles-e-leiserson-harald-prokop-keith-h-randall-mit-laboratory-for-computer-science-cam.html