33,008
社区成员
发帖
与我相关
我的任务
分享擂台赛：计算n!(阶乘)的精确值，速度最快者2000分送上（续)
原贴见http://expert.csdn.net/Expert/topic/2267/2267097.xml
因已经超过回复最大限制（30个)，故只能令开新贴。
我的高级算法出来了，下面是我的计算阶乘各种版本的程序在PIII 733上的运行速度：
10000！ 30000！ 100000！
1.0版 4.93s 50.71s 787.45
1.1版 1.41s 14.46s 184.15s
1.2版 0.77s 7.91s 191.94s
2.0版 0.20s 2.26s 33.28s (中级算法)
3.0版 0.07s 0.55s 3.98s (高级算法)
如果先分解因数再进行乘积运算，可能速度会更快，目前程序尚未完成，等有空儿，我会将这个程序完成，定为3.5版。
因已经超过回复最大限制（30个)，故只能令开新贴。
我的高级算法出来了，下面是我的计算阶乘各种版本的程序在PIII 733上的运行速度：
10000！ 30000！ 100000！
1.0版 4.93s 50.71s 787.45
1.1版 1.41s 14.46s 184.15s
1.2版 0.77s 7.91s 191.94s
2.0版 0.20s 2.26s 33.28s (中级算法)
3.0版 0.07s 0.55s 3.98s (高级算法)
如果先分解因数再进行乘积运算，可能速度会更快，目前程序尚未完成，等有空儿，我会将这个程序完成，定为3.5版。
...全文
请发表友善的回复…
发表回复
liangbch 2004-03-26
- 打赏
- 举报
我昨天晚上和今天早上，对我的一个帖子：http://expert.csdn.net/Expert/TopicView1.asp?id=2427925 进行结贴，总共结贴次数超过10次，每次在输入密码完毕，进行提交时，当打开一个新的网页时，IE 提示，不能找到网页。
在中午，我打开csdn,发现我的帖子竟然结贴了，但是各人的得分并不是我给的分，最奇怪的是：我自己也得了好几次分，这是csdn的毛病，大家不要骂我啊！
在中午，我打开csdn,发现我的帖子竟然结贴了，但是各人的得分并不是我给的分，最奇怪的是：我自己也得了好几次分，这是csdn的毛病，大家不要骂我啊！
xstring 2004-03-25
- 打赏
- 举报
楼主说过了，是分治
估计算法和gmp库里面的算法一样
目前大数乘法还没有哪个能超得过gmp
估计算法和gmp库里面的算法一样
目前大数乘法还没有哪个能超得过gmp
zzwu 2004-03-25
- 打赏
- 举报
此贴要赶快结了,不管有否结果,否则要扣信誉分了!
hanyimath 2004-03-25
- 打赏
- 举报
up
z07165864809 2004-03-25
- 打赏
- 举报
to xstring(麻雀):
光知道分治没有用啊！我想知道的是怎么处理由一位变到若干位的？而且，在最后的几次乘法中，按照理论来说，应该使用FFT更快一点，不知道楼主使用没有？
光知道分治没有用啊！我想知道的是怎么处理由一位变到若干位的？而且，在最后的几次乘法中，按照理论来说，应该使用FFT更快一点，不知道楼主使用没有？
xstring 2004-03-24
- 打赏
- 举报
你说的好象是威尔逊定理吧
n是素数的充分必要条件是 (n-1)! mod n == n-1
如果n是个大数的话，根本行不通啊，算算小数还算过得去
n是素数的充分必要条件是 (n-1)! mod n == n-1
如果n是个大数的话，根本行不通啊，算算小数还算过得去
z07165864809 2004-03-24
- 打赏
- 举报
我把上面的代码改成汇编的，结果就只有30多秒了（533+windows2003)。
下面是代码。
for(l=0;l<k;l++)
{
temp=(unsigned _int64)data[l]*j+carry;
data[l]=temp;
carry=temp>>32;
}
对应的汇编是（其他代码不改动）：
_asm
{
mov esp1,esp //保存esp
xor esp,esp //esp=0; esp作为进位
xor edi,edi //edi=0;
mov esi,k //esi=k;
nextl:
cmp edi,esi //if (edi>=esi) goto out1;
jae out1
mov eax,j //eax=j;
mov ebx,dword ptr [data+edi*4] //ebx=data[l];
mul ebx //edx_eax=ebx*eax
add eax,esp //eax=eax+esp 加上进位
adc edx,0 //edx=edx+cf(进位）
mov dword ptr [data+edi*4],eax //data[l]=eax;
mov esp,edx //esp=edx;
inc edi //edi++;
jmp nextl
out1:
mov carry,esp
mov esp,esp1 //恢复esp
}
这里，我发发现一个问题：在vc中难道不能用pop么？我一用就说我错误，所以我只好用上面的mov来替代了。有高手告诉我原因么？谢谢了。
to xstring(麻雀) :
不知道你说的是我哪个行不通？
第一个，算法是一般的大数库中用的一位乘以多位的算法。这个可以证明其正确性。
第二，费尔马素性（书上不是这么叫的，只是我为了记忆这么叫）检验要求的就是k!的精确值，所以，我怀疑可以用楼主的快速算法计算的。
下面是代码。
for(l=0;l<k;l++)
{
temp=(unsigned _int64)data[l]*j+carry;
data[l]=temp;
carry=temp>>32;
}
对应的汇编是（其他代码不改动）：
_asm
{
mov esp1,esp //保存esp
xor esp,esp //esp=0; esp作为进位
xor edi,edi //edi=0;
mov esi,k //esi=k;
nextl:
cmp edi,esi //if (edi>=esi) goto out1;
jae out1
mov eax,j //eax=j;
mov ebx,dword ptr [data+edi*4] //ebx=data[l];
mul ebx //edx_eax=ebx*eax
add eax,esp //eax=eax+esp 加上进位
adc edx,0 //edx=edx+cf(进位）
mov dword ptr [data+edi*4],eax //data[l]=eax;
mov esp,edx //esp=edx;
inc edi //edi++;
jmp nextl
out1:
mov carry,esp
mov esp,esp1 //恢复esp
}
这里，我发发现一个问题：在vc中难道不能用pop么？我一用就说我错误，所以我只好用上面的mov来替代了。有高手告诉我原因么？谢谢了。
to xstring(麻雀) :
不知道你说的是我哪个行不通？
第一个，算法是一般的大数库中用的一位乘以多位的算法。这个可以证明其正确性。
第二，费尔马素性（书上不是这么叫的，只是我为了记忆这么叫）检验要求的就是k!的精确值，所以，我怀疑可以用楼主的快速算法计算的。
z07165864809 2004-03-24
- 打赏
- 举报
我建议楼主你把你的计算思想告诉大家吧。
看源代码太复杂，往往理解不够透彻。
看源代码太复杂，往往理解不够透彻。
鹿晗表哥 2004-03-24
- 打赏
- 举报
依我看啥时候吧贴子结了分给了然后再开一个讨论
z07165864809 2004-03-24
- 打赏
- 举报
to liangbch(宝宝):
把16进制转化为10进制好困难啊！
果然如兄弟所说。
100000！化为10进制，居然花了100来秒！比计算还慢如干倍。
还有，汇编其实我很了解。
我也知道vc++用了那些register，没有用哪些。
或许是我很就没有使用pop的指令了，反正就不会用了。
就是，我使用pushad/popad居然也报错。
这个才是问题的关键。有没有人能回答啊？？
把16进制转化为10进制好困难啊！
果然如兄弟所说。
100000！化为10进制，居然花了100来秒！比计算还慢如干倍。
还有，汇编其实我很了解。
我也知道vc++用了那些register，没有用哪些。
或许是我很就没有使用pop的指令了，反正就不会用了。
就是，我使用pushad/popad居然也报错。
这个才是问题的关键。有没有人能回答啊？？
z07165864809 2004-03-24
- 打赏
- 举报
to xstring(麻雀) :
不是你认为的这个定理。是使用的费尔马定理的检验（具体的可以参见《算法数论》（中科院的计算机研究生教材，裴定一、祝越飞编写，科学出版社））。
由于求n!的算法和我想编写的RSA中的乘法没有特别大的联系。所以，我只能看大家的算法了，自己没有时间来想了。
不是你认为的这个定理。是使用的费尔马定理的检验（具体的可以参见《算法数论》（中科院的计算机研究生教材，裴定一、祝越飞编写，科学出版社））。
由于求n!的算法和我想编写的RSA中的乘法没有特别大的联系。所以，我只能看大家的算法了，自己没有时间来想了。
liangbch 2004-03-24
- 打赏
- 举报
to z07165864809(不死鸟):
1.按照惯例，esp,ebp 寄存器主要是为了访问 局部变量的和函数调用，编译器生成的代码中，除了函数入口和出口外，几乎不修改esp，ebp寄存器，在你的代码中，修改了esp 寄存器，这是如果发生函数调用的话，一定会出错。
2.你的代码中，确实使用的是2进制，准确地说是2^32进制，这个算法没有用到除法指令，因为64位/32位 除法指令要比32*32位 慢3-4倍，64位/64位除法就更慢了。我的1.0程序中用到了64位/64位除法，1.1版用的是64位/32位 除法，所以你的这个程序的运算速度比我的快这么多倍是完全正常的，没有什么奇怪的。
1.x系列使用的是普通的运算，一般人都可以想的到，2.0依然是用10进制表示法，但是速度提高了好多倍，这就需要一些技巧和算法了，而3.0版则需要的是更好的，也更加复杂的算法。
1.按照惯例，esp,ebp 寄存器主要是为了访问 局部变量的和函数调用，编译器生成的代码中，除了函数入口和出口外，几乎不修改esp，ebp寄存器，在你的代码中，修改了esp 寄存器，这是如果发生函数调用的话，一定会出错。
2.你的代码中，确实使用的是2进制，准确地说是2^32进制，这个算法没有用到除法指令，因为64位/32位 除法指令要比32*32位 慢3-4倍，64位/64位除法就更慢了。我的1.0程序中用到了64位/64位除法，1.1版用的是64位/32位 除法，所以你的这个程序的运算速度比我的快这么多倍是完全正常的，没有什么奇怪的。
1.x系列使用的是普通的运算，一般人都可以想的到，2.0依然是用10进制表示法，但是速度提高了好多倍，这就需要一些技巧和算法了，而3.0版则需要的是更好的，也更加复杂的算法。
yuwengfanshu 2004-03-24
- 打赏
- 举报
可否给我发一封，强烈感谢。
noip@tom.com
noip@tom.com
liangbch 2004-03-24
- 打赏
- 举报
to z07165864809(不死鸟):
在vc中没有必要用asm 书写整个函数，一种聪明的做法是，用C语言做框架，包括定义变量，声明函数参数类型及其返回值，这样编译器自动会生成函数入口和退出指令，包括典型的 push esp ;mov ebp,esp ;退出时sub esp,x ,mov esp,ebp 等。
如果自己来做，一方面很麻烦，二是极容易出错。
在vc中没有必要用asm 书写整个函数，一种聪明的做法是，用C语言做框架，包括定义变量，声明函数参数类型及其返回值，这样编译器自动会生成函数入口和退出指令，包括典型的 push esp ;mov ebp,esp ;退出时sub esp,x ,mov esp,ebp 等。
如果自己来做，一方面很麻烦，二是极容易出错。
F42001 2004-03-24
- 打赏
- 举报
能给我发一份吗？
急需。谢谢。
楼主很牛比啊，IT界多你这种人就好了。
急需。谢谢。
楼主很牛比啊，IT界多你这种人就好了。
xstring 2004-03-23
- 打赏
- 举报
to z07165864809(不死鸟)
根本行不通
根本行不通
z07165864809 2004-03-23
- 打赏
- 举报
呵呵，我突然想起费尔马素数检验来了。
说不定，楼主的这个阶乘算法可以用到这个上面去呢！
（不知道会不会比椭圆曲线素性检验快呢？我说的是现实中的，不是理论上。）
说不定，楼主的这个阶乘算法可以用到这个上面去呢！
（不知道会不会比椭圆曲线素性检验快呢？我说的是现实中的，不是理论上。）
z07165864809 2004-03-23
- 打赏
- 举报
好吧。我把我的代码写出来。
使用的存储方式是最流行的大数存储方式。（如果不明白，请看我的“由RSA引出的问题＂这个贴。
上面的数字错了。
我刚发现。
100,000应该是47398*8位（１６进制）。
for(j=2;j<=i;j++)
{
for(l=0;l<k;l++)
{
temp=(unsigned _int64)data[l]*j+carry;
data[l]=temp;
carry=temp>>32;
}
if(carry>0)
{
k++;
data[k-1]=carry;
}
carry=0;
}
k是当前的数据位数。i=100000.carry为进位。
因为我加入了判断打印的代码，上面的运行时间其实是１２０多秒(piii 533,windows 2003)。
使用的存储方式是最流行的大数存储方式。（如果不明白，请看我的“由RSA引出的问题＂这个贴。
上面的数字错了。
我刚发现。
100,000应该是47398*8位（１６进制）。
for(j=2;j<=i;j++)
{
for(l=0;l<k;l++)
{
temp=(unsigned _int64)data[l]*j+carry;
data[l]=temp;
carry=temp>>32;
}
if(carry>0)
{
k++;
data[k-1]=carry;
}
carry=0;
}
k是当前的数据位数。i=100000.carry为进位。
因为我加入了判断打印的代码，上面的运行时间其实是１２０多秒(piii 533,windows 2003)。
liangbch 2004-03-23
- 打赏
- 举报
把你的代码发给我，我查一查。liangbch@263.net
另外, 只是猜想，
1.你是用的是2进制表示法，在计算过程中不用除法，自然很快，我的算法使用10进制，所以计算的慢了点，但是输出很快。
2. 仔细检查一下你的计算结果，看看是否正确。
另外, 只是猜想，
1.你是用的是2进制表示法，在计算过程中不用除法，自然很快，我的算法使用10进制，所以计算的慢了点，但是输出很快。
2. 仔细检查一下你的计算结果，看看是否正确。
z07165864809 2004-03-23
- 打赏
- 举报
楼主，我对于你的1。0版本很有兴趣，因为我使用最次的一位位的乘再加，在PIII 533上面都只要154秒（共有47403*8位，这里是16进制），你是怎么做到在733上的787秒的？？
呵呵，笑话了。
最近刚好因为RSA的问题，自己拼命的在找乘法的最快方式。所以，一定来捧场。
呵呵，笑话了。
最近刚好因为RSA的问题，自己拼命的在找乘法的最快方式。所以，一定来捧场。
加载更多回复（104）
