Wiki

User Tools

Site Tools

Trace: • debugging_apache_web_server_problems • tax_laws_for_south_african_expats • alter_column • drop_columns • non-root_user_cannot_ping
chess:programming:de_bruijn_sequence

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
chess:programming:de_bruijn_sequence [2021/10/28 14:31] – peterchess:programming:de_bruijn_sequence [2021/10/30 16:52] (current) – peter
Line 1: Line 1:
 ====== Chess - Programming - de Bruijn Sequence ====== ====== 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. 
 + 
 +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. 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). +  * 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.   * 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).+----
  
-  * There are 64 times more sequences by rotating the initial one. +===== De Bruijn for B(2,4) =====
-  * So in total 2^32 possible 64*6bit De Bruijn Sequences!+
  
 +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>
  
 ---- ----
  
-[[Chess:Programming:de Bruijn Sequence:About De Bruijn Sequences|About De Bruijn Sequences]]+Taking each 4-bits
  
-[[Chess:Programming:de Bruijn Sequence:De Bruijn Sequence Generator|De Bruijn Sequence Generator]]+<code> 
 +0000100110101111 
 +</code>
  
-[[Chess:Programming:de Bruijn Sequence:Get De Bruijn Sequence|Get De Bruijn Sequence]]+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>
  
 ---- ----
  
-===== B(2, 6) =====+===== de Bruijn values =====
  
-De Bruijn sequences can be described by two parameters:+^n^de Bruijn^ 
 +|1|01| 
 +|2|1100| 
 +|3|00010111| 
 +|3|01110100| 
 +|4|0000100110101111| 
 +|4|1111011001010000| 
 +|5|11010100111011000101111100100000| 
 +|6|0000001000011000101001111010001110010010110111011001101010111111|
  
-  * **k**: The number of entities in the alphabet e.g. {0,1,2,3,4,5,6,7,8,9} for k=10 +----
-  * **n**: the order (length of sub-sequence required) e.g. n=4 for a four digit long PIN.+
  
 +[[Chess:Programming:de Bruijn Sequence:About De Bruijn Sequences|About De Bruijn Sequences]]
  
-**B(2, 6)** implies 2^6 or 64 bit sequences.+[[Chess:Programming:de Bruijn Sequence:De Bruijn Sequence Generator|De Bruijn Sequence Generator]]
  
-  * There are 2^26 or 67,108,864 odd 64-bit sequences with 64 overlapping unique six-bit sub-sequences, for instance 0x022fdd63cc95386d.+[[Chess:Programming:de Bruijn Sequence:De Bruijn Sequence on a Chess Board|De Bruijn Sequence on a Chess Board]]
  
-<code> +[[Chess:Programming:de Bruijn Sequence:Get De Bruijn Sequence|Get De Bruijn Sequence]]
- i  0000001000101111110111010110001111001100100101010011100001101101|00000 s[i] +
- 0  000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  0 +
- 1   000001                                                                 1 +
- 2  . 000010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  2 +
- 3     000100                                                               4 +
- 4  . . 001000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  8 +
- 5       010001                                                            17 +
- 6  . . . 100010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 +
- 7         000101                                                           5 +
- 8  . . . . 001011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 +
- 9           010111                                                        23 +
-10  . . . . . 101111 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 +
-11             011111                                                      31 +
-12  . . . . . . 111111 . . . . . . . . . . . . . . . . . . . . . . . . . . 63 +
-13               111110                                                    62 +
-14  . . . . . . . 111101 . . . . . . . . . . . . . . . . . . . . . . . . . 61 +
-15                 111011                                                  59 +
-16  . . . . . . . . 110111 . . . . . . . . . . . . . . . . . . . . . . . . 55 +
-17                   101110                                                46 +
-18  . . . . . . . . . 011101 . . . . . . . . . . . . . . . . . . . . . . . 29 +
-19                     111010                                              58 +
-20  . . . . . . . . . . 110101 . . . . . . . . . . . . . . . . . . . . . . 53 +
-21                       101011                                            43 +
-22  . . . . . . . . . . . 010110 . . . . . . . . . . . . . . . . . . . . . 22 +
-23                         101100                                          44 +
-24  . . . . . . . . . . . . 011000 . . . . . . . . . . . . . . . . . . . . 24 +
-25                           110001                                        49 +
-26  . . . . . . . . . . . . . 100011 . . . . . . . . . . . . . . . . . . . 35 +
-27                             000111                                       7 +
-28  . . . . . . . . . . . . . . 001111 . . . . . . . . . . . . . . . . . . 15 +
-29                               011110                                    30 +
-30  . . . . . . . . . . . . . . . 111100 . . . . . . . . . . . . . . . . . 60 +
-31                                 111001                                  57 +
-32  . . . . . . . . . . . . . . . . 110011 . . . . . . . . . . . . . . . . 51 +
-33                                   100110                                38 +
-34  . . . . . . . . . . . . . . . . . 001100 . . . . . . . . . . . . . . . 12 +
-35                                     011001                              25 +
-36  . . . . . . . . . . . . . . . . . . 110010 . . . . . . . . . . . . . . 50 +
-37                                       100100                            36 +
-38  . . . . . . . . . . . . . . . . . . . 001001 . . . . . . . . . . . . .  9 +
-39                                         010010                          18 +
-40  . . . . . . . . . . . . . . . . . . . . 100101 . . . . . . . . . . . . 37 +
-41                                           001010                        10 +
-42  . . . . . . . . . . . . . . . . . . . . . 010101 . . . . . . . . . . . 21 +
-43                                             101010                      42 +
-44  . . . . . . . . . . . . . . . . . . . . . . 010100 . . . . . . . . . . 20 +
-45                                               101001                    41 +
-46  . . . . . . . . . . . . . . . . . . . . . . . 010011 . . . . . . . . . 19 +
-47                                                 100111                  39 +
-48  . . . . . . . . . . . . . . . . . . . . . . . . 001110 . . . . . . . . 14 +
-49                                                   011100                28 +
-50  . . . . . . . . . . . . . . . . . . . . . . . . . 111000 . . . . . . . 56 +
-51                                                     110000              48 +
-52  . . . . . . . . . . . . . . . . . . . . . . . . . . 100001 . . . . . . 33 +
-53                                                       000011             3 +
-54  . . . . . . . . . . . . . . . . . . . . . . . . . . . 000110 . . . . .  6 +
-55                                                         001101          13 +
-56  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 011011 . . . . 27 +
-57                                                           110110        54 +
-58  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101101 . . . 45 +
-59                                                             01101|0     26 +
-60  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1101|00  . 52 +
-61                                                               101|000   40 +
-62  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 01|0000  16 +
-63                                                                 1|00000 32 +
-</code>+
  
-----+[[Chess:Programming:de Bruijn Sequence:Using a De Bruijn Sequence|Using a De Bruijn Sequence]]
  
-===== De Bruijn Graph on a Chess Board =====+[[Chess:Programming:de Bruijn Sequence:8-bit Example|8-bit Example]]
  
-A directed De Bruijn Graph of B(2, 6) sequences with Little-Endian Rank-File Mapping board coordinates (a1 = 0, b1 = 1, h8 = 63).+----
  
-  * For topology reasons, almost each node (except a1 and h8) of the graph is de-concentrated and appears twice in the form of two reversed binary trees. +TODO
-  * The leaf outputs join the respective reversed tree. +
-  * Between c6 and f3 is a direct cycle, since 42 is 2*21 and 21 is (2*42 + 1) % 64, with both six-bit pattern reversed - 010101 (21) versus 101010 (42). +
-  * The challenge is to traverse the graph in any way to visit each of the 64 nodes aka squares __exactly once__.+
  
 <code> <code>
-+----------------->---------------a1--------------<-----------------+ +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 
-|                                 b1                                | +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 . 
-|                c1                               d1                | +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. 
-|        e1              f1               g1              h1        | +Only one of these computations can be correct.
-|     +-/  \-+        +-/  \-+         +-/  \-+        +-/  \-+     | +
-|    a2      b2      c2      d2       e2      f2      g2      h2    | +
-|  a3  b3  c3  d3  e3 |f3| g3  h3   a4  b4  c4  d4  e4  f4  g4  h4  | +
-+-a5b5c5d5e5f5g5h5a6b6c6d6e6f6g6h6 a7b7c7d7e7f7g7h7a8b8c8d8e8f8  |  | +
-     ^ ^ ^ ^ ^ ^ ^ ^ ^   ^ ^ ^ ^ ^  ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^  |  | +
-                                                                 |  | +
-+----------------->---------------h8--------------<--------------+  ^ +
-|                                  |                                | +
-|                                 g8                                | +
-|                 +--------------/  \-------------+                 | +
-|                f8                               e8                | +
-^         +-----/  \-----+                 +-----/  \-----+         | +
-|        d8              c8               b8              a8        | +
-|     +-/  \-+        +-/  \-+         +-/  \-+        +-/  \-+     | +
-|    h7      g7      f7      e7       d7      c7      b7      a7    | +
-|  h6  g6  f6  e6  d6 |c6| b6  a6   h5  g5  f5  e5  d5  c5  b5  a5--+ +
-+-h4g4f4e4d4c4b4a4h3g3f3e3d3c3b3a3 h2g2f2e2d2c2b2a2h1g1f1e1d1c1 +
-     ^ ^ ^ ^ ^ ^ ^ ^ ^   ^ ^ ^ ^ ^  ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^+
 </code> </code>
  
 ---- ----
 +
  
 ===== References ===== ===== References =====
Line 151: Line 106:
  
 https://www.chessprogramming.org/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://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
 +
 +
chess/programming/de_bruijn_sequence.1635431472.txt.gz · Last modified: 2021/10/28 14:31 by peter
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki