[擂台] 大数运算基选择测试 相关搜索: 大数, 运算, 选择

无心人

两个二进制数字， bit位长度是28*30*32
分别用28，30，32个bit为一个处理单位
做加法和乘法
测试在不同基选择下的效果
===============================
这么写如果不妥， 你们可提出意见
咱一起商量测试方案

liangbch

应该加上一些限制，如不得使用高级算法，如分治法，toom-cook 算法等。

无心人

28*30*32=26880
除非有贼快的FFT处理器，否则没人敢用FFT
同样Toom-n在这么小，优势也不大
就那个K算法还能加速
如果位数太大
可以考虑做多次测试
28*32， 28*30，30*32各一次

无心人

//我先提交我的函数，由旧代码修改成
//终于接近完美了，不过还有几条指令似乎可以省掉
//怎么省想不出来 ：）
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]
             mov ebp, 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
             mov edi, ebp
             movd dword ptr [ebx], mm0
             mov ebx, eax
             lea esi, [esi+4]
             lea ebx, [ebx+4]
             sub edx, 1
             jnz mbinmul2
             emms
             }
}

gxqcn

建议将测试的bit长度缩小为：7*15*32 = 3360
在 28*30*32bits 时早该用更好的算法了。

无心人

好
同意你的意见
我只管提交我的标准32位乘法
具体测试你们来
：）

无心人

我的代码必须配合一个清零函数
等我写来
：）

liangbch

我打算 完全用C 编写一个程序，看看你的那个使用 SSE2 指令编写的程序能比我的C版的程序快多少。

无心人

有限的很吧
假设我的时间是100
C写的应该在120-160之间

liangbch

原帖由 无心人 于 2008-4-2 11:24 发表


有限的很吧
假设我的时间是100
C写的应该在120-160之间

由那个128bit * 128 bit 帖子，得出一个结论，使用MMX寄存器的版本(96楼)最高可比使用ALU指令的版本(102楼)快2.33倍(在我的电脑上,前者运行时间为400.665,或者运行时间为935.273),也就是说 使用 MMX的版本 加速比 可达 2.33倍.
  退一步,完全使用c的版本性能可以达到102楼的性能, 我的C版程序运行时间应为 你的4#楼那个版本的2.33倍,你说预计可达你的你的版本的120-160%, 这等于承认了基为$2^30$的版本速度为基为$2^32$版本的 146%- 194%.