Двоичное матричное векторное умножение

Question

Я хочу умножить двоичную матрицу 8x8, представленную как 64-разрядное целое число без знака, на 8-разрядный вектор, представленный символом без знака. Однако из-за некоторых других проблем матрица должна быть упорядочена по столбцам, поэтому нет простого сопоставления байтов для простого умножения.

Есть идеи, как ускорить такой расчет? На каждую операцию приходится делать миллиарды таких расчетов.

Умножения производятся над полем из 2 элементов (F-2).

Answer 1

С этой матрицей и векторным представлением, это помогает сделать умножение матриц следующим образом:

(столбец₁... столбец₈) * (v₁... v₈)^T = столбец₁ * v₁ +... + столбец₈ * v₈

где матрица A = (цв₁... цв₈)

и вектор столбца v = (v₁... v₈)^T

Думая об этом дальше, вы можете делать все умножения одновременно, если вы раздуте 8-битный вектор до 64-битного вектора, повторяя каждый бит 8 раз и затем вычисляя P = A & v_inflated, Осталось только добавить (то есть XOR) продуктов.

Простой подход для XORing продуктов:

uint64_t P = calculated products from text above;
uint64_t sum = 0;
for( int i = 8; i; --i )
{
   sum ^= P & 0xFF;
   P >> 8;  
}

Answer 2

У вас есть только 256 векторов! Используйте таблицы поиска для создания правильных битовых масок, тогда ваша логика будет выглядеть примерно так

output_bit_n = bool (matrix [n] & lookup [vector])

Другими словами, ваша справочная таблица может перенести 8-битное значение в 64-битный мир.

Вы можете эффективно упаковать это в результат с помощью команд поворота с переносом, если компилятор не достаточно умен, чтобы оптимизировать (value<<=1)|=result,