大数运算基选择测试

无心人

不公开代码怎么能证明快？

无心人

俺是不会采用你们的进制的 即使你们的快，能快多少呢？ 看到liangbch的blog了 希望能坚持写下去 我的数论变换也希望自己能写下去 我写的不是资料找不到，相关资料上500页呢 如果遇到困难了，肯定是懒惰的原因

liangbch

原帖由 无心人 于 2008-4-9 11:21 发表 俺是不会采用你们的进制的 即使你们的快，能快多少呢？

快了很多，而不是一点儿。 公布代码与否，是作者的自由，特别是一些领先对手的技术，作者一般不愿公布。 至于能否证明是不是更优，没有别的办法，只有靠相互间的信任了。我以我的信誉担保，我的代码没有作弊，如果你确实不相信，也没有办法。 以后，可以考虑提供静态库，供使用者来测试，但静态库也无法保护算法，只能凭借加密，这需要时间。如果大家确实需要它，我可以考虑以后提供给大家一个加密的静态库。 当然，在适当的时候，我也可能公开我的代码。 我在20#提到的6个函数已经全部完成，说明如下： UInt480x480_ALU： 使用经典的算法，算法类似于GMP中的 mul_basecase.c,汇编代码可参照gmp-4.2.2\mpn\x86\pentium\mul_basecase.asm, 只不过是完全的循环展开式，无需递增地址变量，也没有比较/跳转指令。 UInt480x480_ALU2：类似我在 x86上128位二进制乘法最快速算法征解（http://bbs.emath.ac.cn/thread-216-1-1.html） 102楼做法，减少了ADD指令的使用次数，也减少了内存写的次数，速度有所提升，在内存性能较差的PC（如PM） 上，性能提升明些。 UInt480x480_MMX：类似我在 x86上128位二进制乘法最快速算法征解（http://bbs.emath.ac.cn/thread-216-1-1.html） 76楼的代码，也类似楼主在 本帖中4#的做法，使用完全的循环展开，无需递增 地址变量，也没有比较/跳转指令。 UInt480x480_base30_ALU: 基为$2^30$，有点类似UInt480x480_ALU2，采用完全的循环展开。 UInt480x480_base30_MMX： 基为$2^30$，乘法和加法使只使用MMX寄存器。每个循环步 使用 1次32bit 乘。 目前性能最有优异的版本，性能大大提升。 UInt480x480_base30_SSE2： 基为$2^30$，乘法和加法主要在XMM2寄存器中进行，也少量使用MMX寄存器。结果和我过去的预测不同，在P4 上运行，性能大幅领先于UInt480x480_base30_ALU，在PM上运行，性能却低于UInt480x480_base30_ALU。 结论：不过是PM还是PIV，UInt480x480_base30_MMX 都是最快的版本，我之前一直请看了使用 MMX的SSE2指令。在x86上128位二进制乘法最快速算法征解 中，我的76楼的程序脱颖而出。让我第一次见识了使用 MMX寄存器 SSE2指令的威力。

liangbch

贴上测试结果： 在PIV 2.6G cpu上的测试结果： Test function: UInt480x480_ALU(..) 1000000 times... Elapsed time: 1262.801 ms Test function: UInt480x480_ALU2(..) 1000000 times... Elapsed time: 1240.831 ms Test function: UInt480x480_MMX(..) 1000000 times... Elapsed time: 989.584 ms Test function: UInt480x480_base30_ALU(..) 1000000 times... Elapsed time: 1236.035 ms Test function: UInt480x480_base30_MMX(..) 1000000 times... Elapsed time: 393.707 ms Test function: UInt480x480_base30_SSE2(..) 1000000 times... Elapsed time: 544.485 ms 可以看到，在PIV CPU，采用基为$2^30$的版本，竟达到同样使用MMX寄存器的基为 $2^32 $版本的250%，这可不是快了一点点了。 再贴上PM 1.7G 上的测试结果。 Test function: UInt480x480_ALU(..) 1000000 times... Elapsed time: 935.995 ms Test function: UInt480x480_ALU2(..) 1000000 times... Elapsed time: 892.114 ms Test function: UInt480x480_MMX(..) 1000000 times... Elapsed time: 846.011 ms Test function: UInt480x480_base30_ALU(..) 1000000 times... Elapsed time: 695.499 ms Test function: UInt480x480_base30_MMX(..) 1000000 times... Elapsed time: 562.144 ms Test function: UInt480x480_base30_SSE2(..) 1000000 times... Elapsed time: 912.002 ms

无心人

MMX 32bit乘和我的预期差别太大啊 一个双字乘是12个周期 12 * 225 * 1000000 / 2.6G = 0.137ms ============================== 你的480代表480bit么？

liangbch

由那个帖子：x86上128位二进制乘法最快速算法征解 76#的结果： Test function: UInt128x128To256_SSE2_76F(..) 10000000 times... Elapsed time: 395.657 ms 得到的结论是 1千万 * 4*4=395.657 ms,故平均每次乘是0.00247285625微妙。 按此换算。15*15*0.00247285625*100万=556.39265625ms， 这里的结果是 989.584ms，因为在本例中，没有那么多的寄存器保存中间结果，故需要大量的内存写，时间从估计值556.3926562 变为 989.584 应属正常。没什么不正常呀。

无心人

把程序里所有base30的去掉 源代码给我 =========================== 为什么有疑惑呢 因为无论进制如何 乘法每个循环都是一个乘两个加 而且都不需要考虑进位 一个乘法延迟PM是3，P4是8 P4D是9 加法都是1-2的 不考虑别的因素 其结构都是一致的 所以应该32和30的时间差不多 如果你能优化30到这么大 也应该优化32到更多，毕竟32的字节少 ==================================

liangbch

mbinmul3: movd mm2, dword ptr [edi] lea edi, [edi+4] movd mm3, dword ptr [ebx] pmuludq mm2, mm1 paddq mm0, mm3 paddq mm0, mm2 movd dword ptr [ebx], mm0

本想对 yaos的代码进行测试，却发现这是个未经调试过的版本，根本不能工作。当执行的上面的最后指令时，内存写溢出。 建议yaos以后别发未经调试过的代码。

liangbch

原帖由 无心人 于 2008-4-9 14:21 发表 乘法每个循环都是一个乘两个加 ...

这句话不对。 你完全没有悟到其中的道理，所以base30的代码肯定不能给你了，至于其他的那3个函数的代码，我会在今晚公开。

无心人

错在哪里？ =========================== 对了， 你把我代码改成这个就没问题了 先别考虑清零。看执行时间多少？ void lMul_yaos(uint32 *result, uint32 *left, uint32 *right, uint32 sLeft, uint32 sRight) { __asm { mov edx, sLeft mov esi, dword ptr [left] mov edi, dword ptr [right] mov ebx, dword ptr [result] mbinmul2: mov eax, ebx pxor mm0, mm0 mov ecx, sRight movd mm1, dword ptr [esi] movd mm4, edi mbinmul3: movd mm2, dword ptr [edi] lea edi, [edi+4] movd mm3, dword ptr [ebx] pmuludq mm2, mm1 paddq mm0, mm3 paddq mm0, mm2 movd dword ptr [ebx], mm0 psrlq mm0, 32 lea ebx, [ebx+4] sub ecx, 1 jnz mbinmul3 movd edi, mm4 movd dword ptr [ebx], mm0 mov ebx, eax lea esi, [esi+4] lea ebx, [ebx+4] sub edx, 1 jnz mbinmul2 emms } }