能通过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;
   
5.    
   
6.     mask <<= 54;    /* 10^16 < 2^54 */
   
7.     while( mask > b )  /* b >= 1 */
   
8.         mask >>= 1;
   
9.    
   
10.     while( mask >>= 1 )
    
11.     {
    
12.         if (( r <<= 1 ) >= mod ) r -= mod;
    
13.         if (( b & mask ) && (( r += t ) >= mod )) r -= mod;
    
14.     }
    
15. 
    
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 可有新的更好结论？