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位二进制整数素性测试最优化程序讨论

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