Differences

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

--- chess:programming:de_bruijn_sequence:8-bit_example [2021/10/30 18:10] – [The de Bruijn sequence of this 8-bit value] peter
+++ chess:programming:de_bruijn_sequence:8-bit_example [2021/11/30 00:53] (current) – [Explaining the usage of this de Bruijn sequence] peter
@@ Line 3: / Line 3: @@
 An 8-bit value has 8 digits.
-  * The position can be represented by 3 bits
+  * The position can be represented by 3 bits.
+    * Log2(8) = 3.
 ----
@@ Line 41: / Line 42: @@
     * This leaves the most significant 3 bits.
-  * **0x1DU**:  This value has to be calculated through trial-and-error.
+  * **0x1D**:  This value has to be calculated through trial-and-error.
     * In binary is 00011101.  The de Bruijn sequence.
     * Using the binary number and look at it 3 characters at a time, it contains all the sequence numbers with are no duplicates: <code>
@@ Line 54: / Line 55: @@
 ===== The de Bruijn sequence of this 8-bit value =====
-^bit^pop_lsb^pop_lsb * 0x1D^hash (1st 3 bits)^index^
+^bit^pop_lsb^pop_lsb * 0x1D^hash^index^index order^final order^
-|1|1|0001 1101|000|0|
+^:::^:::^:::^(1st 3 bits)^:::^(index + 1)^(bit at index order position)^
-|2|2|0011 1010|001|1|
+|1|1|0001 1101|000|0|1|1|
-|3|4|0111 0100|011|3|
+|2|2|0011 1010|001|1|2|2|
-|4|8|1110 1000|111|7|
+|3|4|0111 0100|011|3|4|3|
-|5|16|1101 0000|110|6|
+|4|8|1110 1000|111|7|8|7|
-|6|32|1010 0000|101|5|
+|5|16|1101 0000|110|6|7|6|
-|7|64|0100 0000|010|2|
+|6|32|1010 0000|101|5|6|5|
-|8|128|1000 0000|100|4|
+|7|64|0100 0000|010|2|3|7|
+|8|128|1000 0000|100|4|5|4|
 <WRAP info>
@@ Line 71: / Line 73: @@
   * **hash**:  Uses the first 3 bits from the previous step, **pop_lsb * 0x1D**.
   * **index**:  The number represented by the hash.
+  * **index order**:  The sequence of the numbers.
+  * **final order**:  The bit at the position of the **index order**.
   * Prepare an array with the corresponding number of digits at this position.
@@ Line 76: / Line 80: @@
 constexpr int table [8] = { 1 , 2 , 7 , 3 , 8 , 6 , 5 , 4 };
 </code>
+  * This table is made by using the **index order** to determine the next number from the **final order** columns.
+  * The de Bruijn sequence must start with the first digit, the 0 element.
+    * This is to prevent overflow and to allow the whole to circulate naturally during multiplication (left shift operation).
+</WRAP>
+----
+===== Explaining the usage of this de Bruijn sequence =====
+<code cpp>
+constexpr int table [8] = { 1 , 2 , 7 , 3 , 8 , 6 , 5 , 4 };
+</code>
+The c++ code above performs the following function.
+  * It takes a number from 1 to 8 to lookup.
+  * It multiplies this number by 0x1D, which is 29 Decimal.  This is the Magic Number.
+  * It right-shifts this by 5 to determine the specific bit position of that lookup value.
+^Lookup^Lookup multiple by the magic number^Right-shifted by the offset^
+^:::^(29 in this example)^(5 in this example)^
+|1|29|0|
+|2|58|1|
+|7|203|6|
+|3|87|2|
+|8|232|7|
+|6|174|5|
+|5|145|4|
+|4|116|3|
+<WRAP info>
+**NOTE:** This shows that:
+  * A lookup of **1** returns 0, which is the first bit.
+  * A lookup of **2** returns 1, which is the second bit.
+  * A lookup of **3** returns 2, which is the third bit.
+  * ...and so on.
+Every lookup returns a unique and distinct value.
 </WRAP>
@@ Line 88: / Line 133: @@
   * However there may be other **magic numbers** that might also work.
   * As long as a valid De Bruijn sequence is determined that uniquely provides the bit sequences this could be used instead.
+</WRAP>
+----
+===== Hash Function Calculation  =====
+<code>
+hash(x) = (x ∗ dEBRUIJN) >> SHIFT
+</code>
+<WRAP info>
+**NOTE:**
+  * **N**: is the width of the unsigned integer type.
+  * **dEBRUIJN**: is the appropriate de Bruijn sequence of length to exhaust the combination of characters being used, 0, 1.
+  * **SHIFT**:  Can be calculated using this formula:  **(int)(N − Log2(N))**.
+    * Using the 8-bit example:
+      * Log2(8) = 2.40823996531
+      * 8 - 2.40823996531 = 5.59176003469
+      * Round down to make an integer results in 5.
 </WRAP>