Menu
I want to multiply a 8x8 binary matrix represented as a unsigned 64 bit integer by a 8 bit vector represented by a unsigned char. However, due to some other issues the matrix must be ordered by columns, ergo there's no easy matching of bytes for easy multiplication.
Any idea how to speed up such a calculation? Every operation counts for I need billions of such calculations made.
The multiplications are made over a 2 element field (F-2).
897
To define multiplication between a matrix A and a vector x (i.e., the matrix-vector product), we need to view the vector as a column matrix. We define the matrix-vector product only for the case when the number of columns in A equals the number of rows in x.
As a “row-wise”, vector-generating process: Matrix-vector multiplication defines a process for creating a new vector using an existing vector where each element of the new vector is “generated” by taking a weighted sum of each row of the matrix using the elements of a vector as coefficients.
With this matrix and vector representation, it helps to do matrix multiplication this way:
(col1 ... col8) * (v1 ... v8)T = col1 * v1 + ... + col8 * v8
where matrix A = (col1 ... col8)
and column vector v = (v1 ... v8)T
Thinking this further, you can do all multiplications at once if you inflate the 8-bit vector to a 64-bit vector by repeating every bit 8 times and then calculating P = A & v_inflated. The only thing left then, is the addition (i.e. XOR) of the products.
A simple approach for XORing the products is.
uint64_t P = calculated products from text above;
uint64_t sum = 0;
for( int i = 8; i; --i )
{
sum ^= P & 0xFF;
P >> 8;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
