64位二进制整数素性测试最优化程序讨论
和tprime讨论他的多生素数的筛选程序我提出何不筛选部分素数
然后用素性检测程序直接筛选掉余下的候选的
那么就有个问题
64位二进制整数在x86 P4以上级别的CPU上
最优化的算法能否一秒钟测试20000以上的整数？
现在老规矩
SSE2以下架构汇编， C/C++语言
实现一个米勒－罗宾测试
随机测试10000个不同的64位二进制整数
时间越少越好 我的估计
2.0G以上主频的老内核
1.5G以上的新内核
至少能每秒测试50000个整数 你可以自己估算一下, 10^16 以内孪生素数个数为 10304195697298
如果只筛除部分素数, 再用每秒高达 10^5个 测试素性程序去找满足
的条件素数, 最少时间为 10304195697298 / 3600 / 10^5 = 28622 小时.
实际需要的时间比这多的多, 这种大范围情况下还不如直接筛
另外对于K > 8 的K生素数, 你的想法在我的程序中能大幅提升性能
我已经优化到2000小时左右,采用L2大的CPU性能提升明显 :)
也就是说，素性检测程序必须提高到每秒1000万次？？ 能达到1万次已经很强了,
10万属于非常强, 至于1000万还是等待若干年后几百个core的CPU :)
不会的
只要64位普及
64位程序我想每秒测试100万还是可以的
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
另外，不知你程序说2000小时，是如何估算的？ 算法的特殊性所以时间能比较精确的计算出,
我给你发一个规模10^12 孪生素数计算,10^13 6生素数计算 欢迎测试, 最好是双核大L2 的PC 只有个双CPU双线程的服务器可用
呵呵
家里机器是ubuntu 8.04
页:
[1]