我想找到一种尽可能快的方法来乘以两个小布尔矩阵,其中小的意思是8x8,9x9 ... 16x16.这个例程将被大量使用,因此它需要非常高效,所以请不要建议直截了当的解决方案应该足够快.
对于特殊情况8x8和16x16,我已经有了相当高效的实现,基于此处的解决方案,我们将整个矩阵视为uint64_t或uint64_t[4]分别处理.在我的机器上,这比直接实现快大约70-80倍.
但是,在8 <k <16的情况下,我真的不知道如何利用任何合理的表示来实现上述巧妙的技巧.
基本上,我对使用任何类型的表示(矩阵)和函数签名的任何建议持开放态度.您可以假设这是针对32位或64位架构(选择最适合您的建议)
我在问是否可以通过按位运算来改善相当大的整数矩阵乘法。矩阵很小，元素是小的非负整数（small表示最多20个）。
为了使我们专注，我们要非常具体，说我有两个3x3矩阵，它们的整数项0 <= x <15。
以下简单的C ++实现执行了100万次，执行时间约为1s（以linux衡量）time。
#include <random>
int main() {
//Random number generator
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<> distr(0, 15);
int A[3][3];
int B[3][3];
int C[3][3];
for (int trials = 0; trials <= 1000000; trials++) {
//Set up A[] and B[]
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
A[i][j] = distr(eng);
B[i][j] = distr(eng);
C[i][j] = 0;
}
} …