问题：

二进制矩阵乘法位旋转黑客

张嘉佑

2023-03-14

嗨，假设您有两个不同的独立的64位二进制矩阵a和T(T)(T是其自身的转置版本，使用转置版本的矩阵允许在乘法期间对T的行而不是列进行操作，这对于二进制算术来说非常酷），并且您想要对这些矩阵进行乘法，唯一的问题是矩阵乘法结果被截断为64位，如果您在某个特定的矩阵单元中屈服于大于1的值，则生成的矩阵单元将包含1，否则0

   A        T
00000001 01111101 
01010100 01100101 
10010111 00010100 
10110000 00011000 <-- This matrix is transposed
11000100 00111110 
10000011 10101111 
11110101 11000100 
10100000 01100010

二进制和传统乘法结果：

 Binary  Traditional
11000100  11000100
11111111  32212121
11111111  32213421
11111111  21112211
11101111  22101231
11001111  11001311
11111111  54213432
11001111  11001211

你如何用上面描述的最有效物质的方法，将这些矩阵相乘？

我试图利用二进制和（即&运算符）而不是对单独的位执行乘法，在这种情况下，我必须为乘法准备数据：

ulong u;

u = T & 0xFF;
u = (u << 00) + (u << 08) + (u << 16) + (u << 24)
  + (u << 32) + (u << 40) + (u << 48) + (u << 56);

现在，通过对两个整数A和U执行二进制和，将得到以下结果：

   A        u        R        C
00000001 01111101 00000001    1
01010100 01111101 01010100    3
10010111 01111101 00010101    3
10110000 01111101 00110000    2
11000100 01111101 01000100    2
10000011 01111101 00000001    1
11110101 01111101 01110101    5
10100000 01111101 00100000    1

var A = ...;
var T = ...; // T == transpose(t), t is original matrix, algorithm works with transposed matrix

var D = 0x8040201008040201UL;

U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56);
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56);
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56);
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56);
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56);
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56);
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56);
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D);

    public static void Main (string[] args){
        ulong U;
        var Random = new Xor128 ();

        var timer = DateTime.Now;

        var A = Random.As<IUniformRandom<UInt64>>().Evaluate();
        var T = Random.As<IUniformRandom<UInt64>>().Evaluate();

        var steps = 10000000;

        for (var i = 0; i < steps; i++) {
            ulong r = 0;

            var d = 0x8040201008040201UL;

            U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56);
            U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56);
            U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56);
            U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56);
            U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56);
            U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56);
            U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56);
            U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d);
        }

        Console.WriteLine (DateTime.Now - timer);


        var m1 = new Int32[8,8];
        var m2 = new Int32[8,8];
        var m3 = new Int32[8,8];

        for (int row = 0; row < 8; row++) {
            for (int col = 0; col < 8; col++) {
                m1 [row, col] = Random.As<IUniformRandom<Int32>> ().Evaluate(0, 1);
                m2 [row, col] = Random.As<IUniformRandom<Int32>> ().Evaluate(0, 1);
                m3 [row, col] = Random.As<IUniformRandom<Int32>> ().Evaluate(0, 1);
            }
        }

        timer = DateTime.Now;

        for (int i = 0; i < steps; i++) {
            for (int row = 0; row < 8; row++) {
                for (int col = 0; col < 8; col++) {
                    var sum = 0;

                    for (int temp = 0; temp < 8; temp++) {
                        sum += m1 [row, temp] * m2 [temp, row];
                    }

                    m3 [row, col] = sum;
                }
            }
        }

        Console.WriteLine (DateTime.Now - timer);
    }

向我显示以下结果：

00:00:02.4035870
00:00:57.5147150

这是在Mac OS X/Mono下23倍的性能提升，谢谢大家

共有1个答案

吕宇定

2023-03-14

我不确定最有效，但这里有一些东西可以尝试。下面的指令序列计算乘积A*t'的主对角线。将T和D旋转8位，重复7次以上的迭代。

// uint64_t A, T;
uint64_t D = UINT64_C(0x8040201008040201);
uint64_t P = A & T;
// test whether each byte is nonzero
P |= P >> 1;
P |= P >> 2;
P |= P >> 4;
P &= UINT64_C(0x0101010101010101);
// fill each nonzero byte with ones
P *= 255;  // or P = (P << 8) - P;
// leave only the current diagonal
P &= D;

类似资料：

旋转位矩阵

假设我使用大小为8的字符数组来表示图像的碰撞掩码。字符的每一位代表一个像素。实际上，对于64x64矩阵，我将使用长[64]阵列。因此，框将显示为： 45度的示例输出应该是这样的，尽管旋转可以是任何角度。这个形状对于45度旋转可能不准确，因为我是用手做的。另一个例子是向右旋转10度？这些值可能是错误的，因为从数学上讲，我不知道它将如何精确旋转，但我认为可以安全地假设，如果每个位的覆盖率超过旧形状
NumPy矩阵乘法

主要内容：逐元素矩阵乘法,矩阵乘积运算,矩阵点积矩阵乘法是将两个矩阵作为输入值，并将 A 矩阵的行与 B 矩阵的列对应位置相乘再相加，从而生成一个新矩阵，如下图所示：注意：必须确保第一个矩阵中的行数等于第二个矩阵中的列数，否则不能进行矩阵乘法运算。图1：矩阵乘法矩阵乘法运算被称为向量化操作，向量化的主要目的是减少使用的 for 循环次数或者根本不使用。这样做的目的是为了加速程序的计算。下面介绍 NumPy 提供的三种矩阵乘法，从而进一步
多矩阵乘法

问题内容：在numpy中，我有N个3x3矩阵的数组。这将是我如何存储它们的示例（我正在提取内容）：我也有一个由3个向量组成的数组，这将是一个示例：我似乎无法弄清楚如何通过numpy将它们相乘，从而实现如下效果：与的形状（在投射到阵列）是。但是，由于速度的原因，列表实现是不可能的。我尝试了各种换位的np.dot，但最终结果没有得到正确的形状。问题答案：使用脚步： 1）保持第一根轴对
C矩阵乘法

我想使用寄存器（逐行信息）通过向量算法创建矩阵乘法。打开外循环4次我有空洞matvec_XMM（双* a，双* x，双* y，整数n，整数磅）函数的问题，它返回了不好的结果，这是算法wchich我必须使用：它是ma代码：
如何将伽罗瓦场矩阵转换为二进制矩阵

我有一个编码器BCH的输出矩阵（3,63），但这个矩阵是伽罗瓦域，我需要将这个伽罗瓦域转换为矩阵二进制，因为matlab将伽罗瓦域中的元素视为字符串，我需要将这些值视为二进制数。我需要将代码列与000010进行比较，。。。对于开关情况或if，但代码矩阵行是伽罗瓦场格式。我的问题是，遵循matlab错误是开关表达式必须是标量或字符向量。
矩阵乘法（Matrix Multiplication）

考虑两个矩阵A和B.如果A是mxn矩阵而B是nxp矩阵，它们可以相乘以产生mxn矩阵C.只有当A中的列数n等于数量时才可以进行矩阵乘法在B.中的行n 在矩阵乘法中，第一矩阵中的行的元素与第二矩阵中的对应列相乘。在得到的矩阵C中的第（i，j）位置中的每个元素是第i行的第i行中的元素与第二矩阵的第 j列中的对应元素的乘积的总和。 MATLAB中的矩阵乘法是使用*运算符执行的。例子 (Exampl

二进制矩阵乘法位旋转黑客

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档