Differences

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

--- chess:programming:de_bruijn_sequence [2021/10/28 14:55] – peter
+++ chess:programming:de_bruijn_sequence [2021/10/30 16:52] (current) – peter
@@ Line 1: / Line 1: @@
 ====== Chess - Programming - de Bruijn Sequence ======
-A **de Bruijn Sequence** can be used to build a "private **bitScanForward** routine, and to get the LSB (Last Significant Bit).
+A **de Bruijn Sequence** represents all possible sequences of a given length in a way that is as __compressed__ as possible.
-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.
+It can be used to build a private **bitScanForward** routine, and to get the LSB (Least Significant Bit).
--bit De Bruijn Sequences are 64(+5 wrapped)-bit strings, containing 64 overlapping unique sub-strings (ld(64)==6-bits).
+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!
-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).
+----
+===== 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:
-  * There are 64 times more sequences by rotating the initial one.
+<code>
-  * So in total 2^32 possible 64*6bit De Bruijn Sequences!
+,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>
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+</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|
 ----
@@ Line 25: / Line 81: @@
 [[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 =====
@@ Line 36: / Line 106: @@
 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