无心人 发表于 2008-4-1 20:52:12

大数运算基选择测试

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

liangbch 发表于 2008-4-1 21:01:16

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

无心人 发表于 2008-4-1 21:09:45

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

无心人 发表于 2008-4-2 07:56:47

//我先提交我的函数，由旧代码修改成
//终于接近完美了，不过还有几条指令似乎可以省掉
//怎么省想不出来 ：）
voidlMul_yaos(uint32*result, uint32*left, uint32*right, uint32 sLeft, uint32 sRight)
{
__asm          {
             mov edx, sLeft
             movesi, dword ptr
             movedi, dword ptr
             movebx, dword ptr
mbinmul2:
             mov eax, ebx
             pxor mm0, mm0
             mov ecx, sRight                        
             movd mm1, dword ptr
             mov ebp, edi
mbinmul3:
             movd mm2, dword ptr
             lea edi,
             movd mm3, dword ptr                         
             pmuludq mm2, mm1
             paddq mm0, mm3
             paddq mm0, mm2
             movd dword ptr , mm0
             psrlq mm0, 32
             lea ebx,
             sub ecx, 1
             jnz mbinmul3
             mov edi, ebp
             movd dword ptr , mm0
             mov ebx, eax
             lea esi,
             lea ebx,
             sub edx, 1
             jnz mbinmul2
             emms
             }
}

gxqcn 发表于 2008-4-2 07:56:49

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

无心人 发表于 2008-4-2 08:26:01

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

无心人 发表于 2008-4-2 09:39:36

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

liangbch 发表于 2008-4-2 11:01:08

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

无心人 发表于 2008-4-2 11:24:19

:D

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

liangbch 发表于 2008-4-2 11:42:42

原帖由 无心人 于 2008-4-2 11:24 发表 http://images.5d6d.net/dz60/common/back.gif
:D

有限的很吧
假设我的时间是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%.
页: [1] 2 3 4 5 6 7
查看完整版本: 大数运算基选择测试