Найдите самую низкую комбинацию XOR

Question

Рассмотрим следующий код:

#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;
}

Внутри кода следующая развернутая функция выполняется многократно в цикле:

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;

В общей сложности 23XOR .

Но реализация плохая.Оптимизированная версия выглядит следующим образом:

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;

Всего получается 15 XOR .

Я ищу алгоритм, который автоматизирует этот шаг и находит решение, которое использует наименьшее число XOR .

Если есть несколько решений, найдите решение с наименьшим количеством памяти для предварительного вычисления.

Если есть еще несколько решений, не имеет значения, какое из них выбрать.

Некоторыедополнительная информация:

• В реальной программе XOR функции могут быть случайными, поскольку они зависят от ввода пользователя.
• Всегда выполняется 16 шагов.
• Число XOR на шаг может быть между 0 и 7. XOR.
• Количество памяти, необходимое для предварительно вычисленных значений, не имеет значения

Я являюсьПотерял немного о том, как написать это.

Answer 1

Давайте сначала поищем абстрактное определение проблемы: у вас есть тип битового вектора длиной 8 бит, который представляет собой комбинацию ваших 8 входных сигналов. Для каждого сигнала у вас есть значение битового вектора, например 10000000 (первый сигнал) или 00100000 (третий сигнал). Эти значения приведены. Вы хотите сгенерировать следующие значения (я пропустил тривиальные):

r[0]  = 10100000
r[1]  = 01010000
r[2]  = 00101000
r[5]  = 00010100
r[8]  = 01011010
r[9]  = 00111010
r[10] = 00011100
r[11] = 00001101
r[12] = 00100100
r[14] = 01111110
r[15] = 00111100

Теперь мы хотим найти минимум комбинаций (выполнений XOR) для генерации этих значений. Это проблема оптимизации. Я не буду приводить полное доказательство наименьшего количества XOR казней здесь, но вот что я получаю:

int i1 = s02 ^ s04; // 01010000 
int i2 = s03 ^ s05; // 00101000
int i3 = s04 ^ s06; // 00010100
int i4 = s05 ^ s07; // 00001010
int i5 = s03 ^ s06; // 00100100
int i6 = i1 ^ i4;   // 01011010
int i7 = i2 ^ i3;   // 00111100
int i8 = s06 ^ s07; // 00000110

r[0]  = s01 ^ s03;
r[1]  = i1;
r[2]  = i2;
r[5]  = i3;
r[8]  = i6;
r[9]  = i7 ^ i8;
r[10] = i3 ^ s05;
r[11] = i4 ^ i8 ^ s08;
r[12] = i5;
r[14] = i6 ^ i5;
r[15] = i7;

14 XOR с.

Чтобы сформулировать общий алгоритм: вы начинаете с набора S={10000000, 01000000, ... , 00000001}. Вам нужна весовая функция, которая сообщает вам стоимость вашего набора. Определите это как: количество XOR с, необходимое для вычисления всех целевых значений из значений в S без сохранения дополнительных временных значений плюс количество значений в S минус 8 (начальные значения). Первая часть весовой функции может быть реализована с помощью грубой силы (найдите все возможные комбинации для значения цели, которые используют каждое значение в S не более одного раза, выберите ту, которая имеет наименьшее количество XOR выполнений).

Чтобы оптимизировать значение вашей весовой функции, вы объединяете два значения из S с XOR и добавляете их к S, давая S1. Выберите те два значения, которые предоставляют наименьшее новое значение весовой функции (опять же, это можно определить методом грубой силы). У S1 теперь есть еще одно значение (которое будет временным, например, i в моем решении). Для создания этого значения требуется один XOR (поэтому весовая функция считает количество значений в S).

Продолжайте этот шаг, пока не найдете новое значение для добавления к S, которое уменьшает значение весовой функции. Результирующий набор содержит начальные значения плюс все временные значения, которые вы должны вычислить. Шаги, которые вы предприняли, расскажут вам, как рассчитать непосредственные значения.

Это жадный алгоритм. Он не обязательно находит минимальное количество XOR с, но показывает вам простой способ, по крайней мере, получить хорошее решение. Возможно, что алгоритм на самом деле всегда находит лучшее решение, но это должно быть доказано. Если вы хотите быть абсолютно уверенным, вы можете выполнить полный обход всех возможных шагов, которые уменьшают значение весовой функции, начиная с начальных значений S. Это будет обход дерева, и дерево будет конечным - поскольку значение не может опуститься ниже 0 - так что оно определенно решаемо.

Answer 2

Мы хотим вычислить r[i]. Он равен максимум 8 входам XOR между ними.
Теперь подумайте об этом: s8 ^ s6 ^ s5 ^ s4 ^ s3 ^ s2 ^ s1, примерно как число 10111111.
1, если мы используем соответствующий s в XORing, 0, если нет.
Мы можем предварительно вычислить все возможные варианты 2 ^ 8:

t[0] = 0       (00000000, nothing)
t[1] = s1      (00000001)
t[2] = s2      (00000010)
t[3] = s2 ^ s1 (00000011)
t[4] = s3      (00000100)
t[5] = s3 ^ s1 (00000101)
...
t[255] = s8 ^ s7 ^ s6 ^ s5 ^ s4 ^ s3 ^ s2 ^ s1 (11111111)

Затем в цикле, если вы хотите, например, вычислить:

r[0] = s1 ^ s3

s1 ^ s3 в нашем представлении - 00000101 = 5, что дает нам индекс для предварительно вычисленной таблицы поиска:

r[0] = t[5]

Это решает вашу проблему без использования XOR в цикле.

Answer 3

То, что вы сделали здесь вручную, на самом деле является классической оптимизацией компилятора, называемой устранение общего подвыражения (CSE).

Прежде чем делать это вручную или использовать инструмент для выполнения CSE наИсходный код, проверьте получившуюся сборку, чтобы увидеть, выполняет ли ваш компилятор CSE для вас.Скорее всего, так и есть, и обратите внимание, что компилятор - это действительно то место, где нужно делать CSE, поскольку есть компромисс, который необходимо сделать: чем активнее вы выполняете CSE, тем больше вы уменьшаете объем вычислений, который вам нужно сделать,но чем больше памяти (т.е. регистров или оперативной памяти) вам нужно.Слишком агрессивное выполнение CSE может фактически повредить производительности, если это заставит вас пролить регистры или увеличить пропускную способность вашей памяти - компилятор, как правило, будет знать, как выполнить этот вид компромисса.