要怎么夸奖你呢 准备穷举10^7内的素数对(p,q)，以改进结果。
哪位给优化一下MultiModular()函数。
另外，无心人以前说过:
原帖由 无心人 于 2008-10-10 07:53 发表 http://bbs.emath.ac.cn/images/common/back.gif
:)
你还在随机抽取？
按我说的算法
假设5000个候选
1秒至少可测试1万个
用C/C++还要多
那么测试10万素数底
只需要5万秒
而最后的两两求与
其工作量是
5000/128
128怎么来的,我这边只是用__int64来做的.
一次基本运算就可以得到128位内的位为1的数量? :)SIMD SSE2 pand
MultiModular 算法改进
请将 19# 的__int64 MultiModular( __int64 a, __int64 b, __int64 mod ){__int64 r=0, t=a%mod;
while( b>0 ){
if( (b&1) && (r=r+t)>mod ) r-=mod;
if( (t<<=1)>mod )t-=mod;
b>>=1;
}
return r;
}修改成如下的：__int64 MultiModular( __int64 a, __int64 b, __int64 mod ){
__int64 t=a%mod;
__int64 r=t;
__int64 mask = 1;
mask <<= 54; /* 10^16 < 2^54 */
while( mask > b )/* b >= 1 */
mask >>= 1;
while( mask >>= 1 )
{
if (( r <<= 1 ) >= mod ) r -= mod;
if (( b & mask ) && (( r += t ) >= mod )) r -= mod;
}
return r;
}效率应更高（注：我未测试；本算法 t 保持不变）。
如果还要优化，则可能需要用到：
1、Montgomery 算法；
2、汇编 优化。 我怎么看蒙哥马利算法里面似乎还有双倍精度计算啊？
呵呵 蒙哥马利算法任意精度都可，
但超长的似乎并不划算，如果无法享用到O(nlogn)级别的大数乘法的话。 :)
我是这个意思
蒙哥马利算64位的模乘
中间是否不再有64位乘了？？
如果有，未必比连续64位减速度快
当然，纯64位环境，直接
mov rax, a
mov rdx, b
mov rbx, mod
mul rdx
divrbx
mov rax, rdx
比什么算法都快
所以不用考虑 原帖由 无心人 于 2008-10-15 08:31 发表 http://bbs.emath.ac.cn/images/common/back.gif
:)
我是这个意思
蒙哥马利算64位的模乘
中间是否不再有64位乘了？？
如果有，未必比连续64位减速度快
当然，纯64位环境，直接
mov rax, a
mov rdx, b
mov rbx, mod
mul rdx
divrbx
mov rax, rdx
比什么算法都快
所以不用考虑
32位下计算64位模乘，用蒙哥马利算法需要的乘法次数比较多，可能确实不划算。
64位下，蒙哥马利算法需要三次乘法，一次比较，1到2次加减法，
如果 div 时钟数远大于 mul，则直接算法不占优。 除法我想不会超过乘法时间的3倍的 medie2005 可有新的更好结论？