二进制矩阵向量乘法

Question

我想将8x8 二进制矩阵乘以由无符号字符表示的8位向量表示为无符号64位整数.但是,由于一些其他问题,矩阵必须按列排序,因此不容易匹配字节以便于乘法.

知道如何加快这样的计算吗？每项操作都是重要的,我需要进行数十亿次这样的计算.

乘法是在2元素场(F-2)上进行的.

Answer 1

使用此矩阵和向量表示,有助于以这种方式进行矩阵乘法:

(col ₁ ... col ₈)*(v ₁ ... v ₈)^T = col ₁*v ₁ + ... + col ₈*v ₈

矩阵A =(col ₁ ... col ₈)

和列向量v =(v ₁ ... v ₈)^T

进一步考虑这一点,如果通过重复每一位8次然后计算将8位向量扩展为64位向量,则可以立即进行所有乘法运算P = A & v_inflated.唯一剩下的就是产品的添加(即异或).

对产品进行异或的简单方法是.

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位世界.

如果编译器不够智能以进行优化,您可以使用rotate-with-carry指令将其有效地打包到结果中(value<<=1)|=result.