大数运算基选择测试

无心人

还没测试呢 别说这么多话 我只是猜测

liangbch

我的建议： 我的打算，编写一个程序，给出 基为 $2^30 $与基为 $2^32 $的速度对比，具体方法如下。 1.数的长度采用15×32=480bit。 2.仿制 x86上128位二进制乘法最快速算法征解 那个帖子中 96楼的程序，写一个480 bit * 480 bit的 SSE2指令 MM 寄存器版，完全循环展开，无循环，无跳转指令，共需15×15共225次 32bit 的乘法。（已经证明，这种算法是最快的版本SSE2指令中最快的版本。 3.仿制x86上128位二进制乘法最快速算法征解 那个帖子中 102楼的程序，写一个480 bit * 480 bit的 ALU版，完全循环展开，无循环，无跳转指令，共需15×15共225次 32bit 的乘法。（已经证明，这种算法是最快的ALU版,具体数据可从gxq x86上 96bit*96 bit 征解的那个帖子。 4.将480bit展开为16个DWORD，每个DWORD表示30bit（即基为$2^30$)，写一个ALU版本的程序，共需16×16=256次乘法。 5.将480bit展开为16个DWORD，每个DWORD表示30bit（即基为$2^30$)，写一个SSE2指令MM寄存器版本（采用32bit乘，64bit加)。共需16×16=256次乘法。 6.将480bit展开为16个DWORD，每个DWORD表示30bit（即基为$2^30$)，写一个SSE2指令XMM寄存器版本（采用128位寄存器，充分发挥SSE2指令优势)。 至于和基为2^28的速度对比，如果gxq愿意的话，可参照如下形式。 1.数的长度采用14×32=448bit。 2.仿制 x86上128位二进制乘法最快速算法征解 那个帖子中 96楼的程序，写一个448 bit * 448 bit的 SSE2指令 MM 寄存器版，完全循环展开，无循环，无跳转指令，共需15×15共225次 32bit 的乘法。（已经证明，这种算法是最快的版本SSE2指令中最快的版本。 3.仿制x86上128位二进制乘法最快速算法征解 那个帖子中 102楼的程序，写一个448 bit * 448 bit的 ALU版，完全循环展开，无循环，无跳转指令，共需14×14共196次 32bit 的乘法。（已经证明，这种算法是最快的ALU版,具体数据可从gxq x86上 96bit*96 bit 征解的那个帖子。 4.将448bit展开为16个DWORD，每个DWORD表示28bit（即基为$2^28$)，写一个ALU版本的程序，共需16×16=256次乘法。 5.可根据需要写1个或者几个SSE2 指令的版本。 几点说明，基准程序（采用基为2^32的版本），公开源代码。其他 基为2^30或者2^28的程序，可不公布源代码。

无心人

不行的 不能完全循环展开 那只是用于小数字的算法 如果你想基于真实环境 请写一个能用于从1-4096bit都能正确工作的版本 可不考虑结果清零过程 结果清零由外部函数完成 我可提供个高于4GB / s的结果清零函数

gxqcn

为了达到实用之目的， 还是不固定乘数的bit长度的好，但可事先约定其上限，以方便算法优化。

无心人

//双字串清零，提高了速度,达到 < 2 Clock / DWORD void AsmMemZero(unsigned long * p, unsigned long t) { __asm { mov ecx, t cmp ecx, 0 je AsmMemZero3 mov eax, dword ptr [p] mov ebx, 0 test eax, 15 //不是16字节对齐的执行下面的语句 je AsmMemZero4 mov edx, eax shr edx, 4 shl edx, 4 cmp edx, eax je AsmMemZero4 add edx, 16 sub edx, eax shr edx, 2 sub ecx, edx AsmMemZero7: mov [eax], ebx add eax, 4 sub edx, 1 jne AsmMemZero7 cmp ecx, 0 je AsmMemZero3 AsmMemZero4: mov ebx, ecx shr ebx, 2 mov edx, ebx shl ebx, 2 cmp ebx, 0 //是否不足16字节 je AsmMemZero6 sub ecx, ebx mov ebx, ecx //保留末尾的不足16字节的部分 mov ecx, edx //循环的次数 pxor xmm0, xmm0 AsmMemZero1: movntdq [eax], xmm0 //t较小用movdqa add eax, 16 loop AsmMemZero1 cmp ebx, 0 je AsmMemZero3 mov ecx, ebx AsmMemZero6: mov ebx, 0 AsmMemZero2: mov [eax], ebx add eax, 4 loop AsmMemZero2 AsmMemZero3: sfence emms } }

liangbch

to gxq 就其应用而言，不固定长度是必须的。但这里我 主要想测试/展示一下这几种做法的速度之比，及理论最佳速度。如果采用不固定长度，可能会使用许多技巧，如循环展开等，使得比较不公平。 to 无心人，清0不是必须的，这样反而浪费时间。 看可一下你的代码，伪代码大抵是这样的。 for (i=0;i>32); } } 总共需要n*n次操作，每次操作包括，一次32bit * 32bit 乘法，2次 64bit和 32bit 的加法。这种做法，需要事先清空result. 将算法作如下修改，就不需要清空result，而且在第一趟计算中，不需对result[ i ]累加，这样节省了不少运行时间。 其实，我的96楼的程序就是这么做的，不知你为什么没有采用这种做法。 //第一趟，不需和result[ i ]累加 c=0; for (j=0;j>32); } result[j]=c; for (i=1;i>32); } result[i+j]=c; } }

无心人

//双字串清零函数最新版本 //已测试比前版速度快 //已测试长度越大，比ALU指令越快 //应该总假定是双字串 void AsmMemZero(unsigned long * p, unsigned long t) { __asm { xor eax, eax cld mov edi, dword ptr [p] mov edx, t test edx, 0xFFFFFFFF je exit0 test edi, 15 //是否16字节对齐 je AsmZero1 mov ecx, edi and ecx, 0xFFFFFFF0 add ecx, 16 sub ecx, edi //得到需要双字复制部分，要和edx比较谁大 shr ecx, 2 //转换为双字长度 mov ebx, ecx cmp ecx, edx ja AsmZero2 //不足，转尾处理 rep stosd sub edx, ebx je exit0 //是否刚好 AsmZero1: //16字节对齐 mov ecx, edx shr ecx, 4 je AsmZero2 //是否不足16字节 pxor xmm0, xmm0 AsmZero11: movdqa [edi], xmm0 add edi, 16 sub ecx, 1 jne AsmZero11 AsmZero2: mov ecx, edx and ecx, 15 rep stosd exit0: sfence } }

无心人

谢谢你的提醒 我会修改的 ======== 顺上刚测试的清零函数共享

无心人

考虑一次乘4个的可能性 如果有效率提高 是否说明比你们算法好？ 至少那个长加你们可能就无法超越吧 毕竟32位是系统自动规整的

liangbch

原帖由 无心人 于 2008-4-8 20:43 发表 考虑一次乘4个的可能性 如果有效率提高 是否说明比你们算法好？ 至少那个长加你们可能就无法超越吧 毕竟32位是系统自动规整的

我准备写3个基为 $2^32 $的版本， 3个基为 $2^30$的版本， 总体说来，后三者一定比前三者快，并且公布前三者的代码（后3者的代码将在适当的时候公开）。 你等着看好消息吧，看看我的版本可比你的版本快多少。