64位二进制整数素性测试最优化程序讨论

无心人 · 发表于 2008-7-12 10:00:09

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

和tprime讨论他的多生素数的筛选程序
我提出何不筛选部分素数
然后用素性检测程序直接筛选掉余下的候选的

那么就有个问题
64位二进制整数在x86 P4以上级别的CPU上
最优化的算法能否一秒钟测试20000以上的整数？
现在老规矩
SSE2以下架构汇编， C/C++语言
实现一个米勒－罗宾测试
随机测试10000个不同的64位二进制整数
时间越少越好

无心人 · 发表于 2008-7-12 10:02:13

我的估计
2.0G以上主频的老内核
1.5G以上的新内核

至少能每秒测试50000个整数

tprime · 发表于 2008-7-12 14:50:10

你可以自己估算一下, 10^16 以内孪生素数个数为 10304195697298
如果只筛除部分素数, 再用每秒高达 10^5个测试素性程序去找满足
的条件素数, 最少时间为 10304195697298 / 3600 / 10^5 = 28622 小时.
实际需要的时间比这多的多, 这种大范围情况下还不如直接筛
另外对于K > 8 的K生素数, 你的想法在我的程序中能大幅提升性能
我已经优化到2000小时左右,采用L2大的CPU性能提升明显

无心人 · 发表于 2008-7-12 14:57:03

也就是说，素性检测程序必须提高到每秒1000万次？？

tprime · 发表于 2008-7-12 15:04:44

能达到1万次已经很强了,
10万属于非常强, 至于1000万还是等待若干年后几百个core的CPU

无心人 · 发表于 2008-7-12 16:11:14

不会的
只要64位普及
64位程序我想每秒测试100万还是可以的
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
另外，不知你程序说2000小时，是如何估算的？

tprime · 发表于 2008-7-12 17:51:41

算法的特殊性所以时间能比较精确的计算出,
我给你发一个规模10^12 孪生素数计算,10^13 6生素数计算

tprime · 发表于 2008-7-12 17:58:34

欢迎测试, 最好是双核大L2 的PC

无心人 · 发表于 2008-7-12 18:26:16

只有个双CPU双线程的服务器可用
呵呵
家里机器是ubuntu 8.04

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 64位二进制整数素性测试最优化程序讨论

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。