c - バイナリ行列ベクトル乗算

Question

符号なし 64 ビット整数として表される 8x8バイナリマトリックスを、符号なし char で表される 8 ビットベクトルで乗算したいと考えています。ただし、他のいくつかの問題により、行列は列ごとに並べ替える必要があるため、簡単に乗算するためにバイトを簡単に一致させることはできません。

そのような計算を高速化する方法はありますか? 何十億もの計算が必要なため、すべての操作が重要です。

乗算は、2 要素フィールド (F-2) に対して行われます。

score 7 · Accepted Answer

この行列とベクトル表現を使用すると、行列の乗算を次のように行うことができます。

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

ここで、行列 A = (列₁ ... 列₈ )

および列ベクトル v = (v ₁ ... v ₈ ) ^T

これをさらに考えてみると、すべてのビットを 8 回繰り返してからを計算することによって 8 ビットベクトルを 64 ビットベクトルに膨張させると、一度にすべての乗算を行うことができますP = A & v_inflated。残っているのは、積の加算 (つまり、XOR) だけです。

積を XOR する簡単な方法は次のとおりです。

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

score 6 · Accepted Answer

ベクトルは 256 個しかありません! ルックアップテーブルを使用して適切なビットマスクを生成すると、ロジックは次のようになります。

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

つまり、ルックアップテーブルは 8 ビット値を 64 ビット世界に転置できます。

コンパイラが(value<<=1)|=result. _

2 に答える 2