StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFind the lowest combination of XOR
text
Body
copied!<p>Consider the following code:</p> <pre><code>#include <stdio.h> #include <stdlib.h> #include <string.h> int main (int argc, char *argv[]) { time_t seed; time (&seed); srand (seed); int i, j, k, l; // init random values s1 .. s8 int s[8]; for (l = 0; l < 8; l++) s[l] = rand (); // zero result int r[16]; for (j = 0; j < 16; j++) r[j] = 0; // do 100 random xor functions for (i = 0; i < 100; i++) { // generates random function to show why CSE must be computed in runtime int steps[16]; for (j = 0; j < 16; j++) steps[j] = rand (); // _here_ is optimization possible // run function MANY times to show that optimization makes sense for (l = 0; l < 1000000; l++) { for (j = 0; j < 16; j++) { int tmp = 0; for (k = 0; k < 8; k++) tmp ^= ((steps[j] >> k) & 1) ? s[k] : 0; r[j] += tmp; } } for (j = 0; j < 16; j++) printf ("%08x\n", r[j]); puts (""); } return 0; } </code></pre> <p>Inside the code, the following unrolled function is executed many times in a loop:</p> <pre><code>r[ 0] += s01 ^ s03; r[ 1] += s02 ^ s04; r[ 2] += s03 ^ s05; r[ 3] += s02; r[ 4] += s03; r[ 5] += s04 ^ s06; r[ 6] += s03; r[ 7] += s04; r[ 8] += s02 ^ s04 ^ s05 ^ s07; r[ 9] += s03 ^ s04 ^ s05 ^ s07; r[10] += s04 ^ s05 ^ s06; r[11] += s05 ^ s06 ^ s08; r[12] += s03 ^ s06; r[13] += s06; r[14] += s02 ^ s03 ^ s04 ^ s05 ^ s06 ^ s07; r[15] += s03 ^ s04 ^ s05 ^ s06; </code></pre> <p>Makes a total of <strong>23 XOR</strong>.</p> <p>But the implementation is bad. An optimized version is this:</p> <pre><code>int s04___s05 = s04 ^ s05; int s03___s06 = s03 ^ s06; int s04___s05___s07 = s04___s05 ^ s07; int s03___s04___s05___s06 = s03___s06 ^ s04___s05; r[ 0] += s01 ^ s03; r[ 1] += s02 ^ s04; r[ 2] += s03 ^ s05; r[ 3] += s02; r[ 4] += s03; r[ 5] += s04 ^ s06; r[ 6] += s03; r[ 7] += s04; r[ 8] += s02 ^ s04___s05___s07; r[ 9] += s03 ^ s04___s05___s07; r[10] += s04___s05 ^ s06; r[11] += s05 ^ s06 ^ s08; r[12] += s03___s06; r[13] += s06; r[14] += s02 ^ s03___s04___s05___s06 ^ s07; r[15] += s03___s04___s05___s06; </code></pre> <p>Makes a total of <strong>15 XOR</strong>. </p> <p>I am searching for an algorithm that automates this step and finds a solution that uses <strong>the lowest number of XOR</strong>. </p> <p>If there are multiple solutions find the one with the lowest number of storage for precomputation.</p> <p>If there are still multiple solution it does not matter which to choose.</p> <p>Some additional informations:</p> <ul> <li>In the real program the XOR's of the function can be random because they depend on user-input.</li> <li>There are always 16 steps done. </li> <li>The number of XOR per step can be between 0 and 7 XOR.</li> <li>The number of storage required for the precomputed values does not matter</li> </ul> <p>I am a bit lost on how to write this.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload