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 • setup_ip_blocking
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/30 13:30] – peterchess:programming:de_bruijn_sequence [2021/10/30 16:52] (current) – peter
Line 16: Line 16:
  
 ===== De Bruijn for B(2,4) ===== ===== 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 Taking each 4-bits
Line 45: Line 55:
 **NOTE:** The last 3 wraps around to the start to get the 4th digit. **NOTE:** The last 3 wraps around to the start to get the 4th digit.
 </WRAP> </WRAP>
 +
 +----
 +
 +===== de Bruijn values =====
 +
 +^n^de Bruijn^
 +|1|01|
 +|2|1100|
 +|3|00010111|
 +|3|01110100|
 +|4|0000100110101111|
 +|4|1111011001010000|
 +|5|11010100111011000101111100100000|
 +|6|0000001000011000101001111010001110010010110111011001101010111111|
  
 ---- ----
Line 57: Line 81:
  
 [[Chess:Programming:de Bruijn Sequence:Using a De Bruijn Sequence|Using a 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 ===== ===== References =====
Line 67: Line 108:
  
 http://supertech.csail.mit.edu/papers/debruijn.pdf 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
Line 73: Line 116:
  
 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 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.1635600606.txt.gz · Last modified: 2021/10/30 13:30 by peter
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki