大数运算基选择测试

无心人

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

无心人

俺是不会采用你们的进制的
即使你们的快，能快多少呢？

看到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
             }
}