- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
您好,假设您有两个不同的独立 64 位二进制矩阵 A
和 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
执行二进制 and
它将产生以下结果:
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
在上面的示例中,R
包含 A
位乘以 u
位的结果,为了获得最终值,我们必须 对一行中的所有位求和
。请注意,C
列包含的值等于在上面生成的 Traditional
矩阵乘法的第一列中找到的值。问题是,在这一步中,我必须对一个单独的位进行操作,我认为这是次优的方法,我已经通读了 http://graphics.stanford.edu/~seander/bithacks.html寻找一种方法来并行执行此操作但没有运气,如果有人对如何将 R
列中的值“展平”和“合并”到生成的 64 位矩阵中有任何想法,我会如果你给我几行,我将不胜感激,
谢谢,
非常感谢 David Eisenstat,最终算法如下所示:
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 倍,谢谢大家
最佳答案
我不确定最效率如何,但可以尝试一下。以下指令序列计算乘积 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;
关于algorithm - 二进制矩阵乘法 bit twiddling hack,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18447321/
是否可以在没有 bit.dev 帐户的情况下将 bit 设置为本地服务器以进行内部处理? 我知道您可能没有相同的功能 -- bit's FAQ page说“与 Bit CLI 不同,bit.dev 服
我是一名计算机科学学生,学习如何用 C 语言编程。我有 3 个文件和一个 Makefile。我有 logic.c logic.h main.c logic.c 的顶部是: #include "log
我有一个特殊的无符号长整型(32 位),我需要一点一点地转换它的字节序 - 我的长整型表示将多个内容混合在一起形成一个二进制文件。 我该怎么做? 最佳答案 字节顺序是一个字级概念,其中字节要么以最高有
我有许多 iOS Xcode 项目都使用同一个子项目。这个子项目构建一个静态库,然后链接到主项目。到目前为止,这个子项目和所有主项目都是 32 位的。 我想构建一个支持 64 位的新项目,因此将架构设
我创建了一个使用 SIMD 执行 64 位 * 64 位到 128 位的函数。目前我已经使用 SSE2(实际上是 SSE4.1)实现了它。这意味着它同时处理两个 64b*64b 到 128b 的产品。
想知道是否有人对我如何对二进制数执行以下操作有一些了解: 转换 01+0 -> 10+1 (+ as in regular expressions, one or more) 01 ->
代码如下: unsigned int v; // word value to compute the parity of v ^= v >> 16; v ^= v >> 8; v ^= v >> 4
我正在尝试在(测试版)Trackmania 2 游戏中制作脚本。(这是 JavaScript、HTML、C 和...其他我在最糟糕的噩梦中无法想象的东西的丑陋混合)。 脚本引擎似乎不知道“and”或“
这个问题在这里已经有了答案: How do AX, AH, AL map onto EAX? (6 个回答) 去年关闭。 所以,假设我正在使用寄存器 %rax和 %rdi . 作为一个基本的例子,让我
我是编程新手,来自非CS背景(没有正式学位)。我主要使用C#编写Winforms。 我对32位和64位感到困惑...。我的意思是,听说过32位OS,32位处理器以及基于程序的最大内存。它如何影响程序的
“清除整数的第 6 位”的最佳方法是什么? 而且,您的解决方案平台是否独立? (32 位或 64 位整数等)。如果没有,您能否提供一个独立于平台的解决方案? 更新: 我们不知道该位在给出时是已设置还是
我刚刚在交错一些 float 时发现了一些狡猾的问题。我简化了问题并尝试了一些测试 #include #include std::vector v; // global instance unio
我不想用这个来骚扰你,但我在互联网上的任何地方都找不到对“位填充”到底是什么的详细解释,也没有找到与位填充相关的线程的任何答案在 StackOverflow 上。 我还在 ISO 9899-1990
我有点卡住了,因为我找不到任何涵盖缓存“数据”部分的内容,我用谷歌搜索的所有内容都涉及 99.9% 的缓存寻址。我被问到的问题是这样措辞的 Contrast the difference betwee
关闭。这个问题需要debugging details .它目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and th
是否有人通过运行/附加到 64 位应用程序成功调试 64 位 dll?我有应用程序和 dll 的 Delphi 代码。我可以调试 32 位和 64 位应用程序。我还可以通过使用 Run -> Para
我有一些使用 native 组件的库,这些库是使用 NDK 为 32 位 Arm 架构构建的。 现在我们在现代设备上有 64 位处理器,所以我想知道这些库是否可以工作。在我的情况下,我没有本地库的源代
这是我上一个问题的延伸 - How to securely and efficiently store SSN in a database? 这个想法是,我想要安全地散列社会安全号码,然后插入到列中,
我很尴尬地说,我的数学技能很弱,而且我是一名自豪的计算机科学专业。我正在上课,这真是太令人难以承受了。这是我家庭作业的一部分,但是,在理解这一部分之前我无法继续。我类的每个人都在努力编写某种方法来完成
在 InnoSetup 中我运行这段代码: J32 := ShellExec('', 'java', '-d32 -version', '', SW_HIDE, ewWaitUntilTerminat
我是一名优秀的程序员,十分优秀!