能通过2，3，5，7的检验的合数

无心人

要怎么夸奖你呢

medie2005

准备穷举10^7内的素数对(p,q)，以改进结果。 哪位给优化一下MultiModular()函数。 另外，无心人以前说过:

原帖由 无心人 于 2008-10-10 07:53 发表 你还在随机抽取？ 按我说的算法 假设5000个候选 1秒至少可测试1万个 用C/C++还要多 那么测试10万素数底 只需要5万秒 而最后的两两求与 其工作量是 5000/128

128怎么来的,我这边只是用__int64来做的. 一次基本运算就可以得到128位内的位为1的数量?

无心人

SIMD SSE2 pand

gxqcn

请将 19# 的

1. __int64 MultiModular( __int64 a, __int64 b, __int64 mod ){
2. __int64 r=0, t=a%mod;
3. while( b>0 ){
4. if( (b&1) && (r=r+t)>mod ) r-=mod;
5. if( (t<<=1)>mod ) t-=mod;
6. b>>=1;
7. }
8. return r;
9. }

复制代码

修改成如下的：

1. __int64 MultiModular( __int64 a, __int64 b, __int64 mod ){
2. __int64 t=a%mod;
3. __int64 r=t;
4. __int64 mask = 1;
6. mask <<= 54; /* 10^16 < 2^54 */
7. while( mask > b ) /* b >= 1 */
8. mask >>= 1;
10. while( mask >>= 1 )
11. {
12. if (( r <<= 1 ) >= mod ) r -= mod;
13. if (( b & mask ) && (( r += t ) >= mod )) r -= mod;
14. }
16. return r;
17. }

复制代码

效率应更高（注：我未测试；本算法 t 保持不变）。 如果还要优化，则可能需要用到： 1、Montgomery 算法； 2、汇编 优化。

无心人

我怎么看蒙哥马利算法里面似乎还有双倍精度计算啊？ 呵呵

gxqcn

蒙哥马利算法任意精度都可， 但超长的似乎并不划算，如果无法享用到O(nlogn)级别的大数乘法的话。

无心人

我是这个意思 蒙哥马利算64位的模乘 中间是否不再有64位乘了？？ 如果有，未必比连续64位减速度快 当然，纯64位环境，直接 mov rax, a mov rdx, b mov rbx, mod mul rdx div rbx mov rax, rdx 比什么算法都快 所以不用考虑

gxqcn

原帖由 无心人 于 2008-10-15 08:31 发表 我是这个意思 蒙哥马利算64位的模乘 中间是否不再有64位乘了？？ 如果有，未必比连续64位减速度快 当然，纯64位环境，直接 mov rax, a mov rdx, b mov rbx, mod mul rdx div rbx mov rax, rdx 比什么算法都快 所以不用考虑

32位下计算64位模乘，用蒙哥马利算法需要的乘法次数比较多，可能确实不划算。 64位下，蒙哥马利算法需要三次乘法，一次比较，1到2次加减法， 如果 div 时钟数远大于 mul，则直接算法不占优。

无心人

除法我想不会超过乘法时间的3倍的

gxqcn

medie2005 可有新的更好结论？