数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[讨论] 估计下找到10^100以上的一个四生素数的工作量

[复制链接]
发表于 2008-2-14 14:07:42 | 显示全部楼层
呵呵,好像也看不出明显的速度区别。
看我这次运行结果SQRTSMALLPRIMES 选择1000
加起来才150秒左右

Filter cost 50432ms
Found n-4,n-2,n+2,n+4 where n is 7 088 374 943 931 040 097 984 829 452 127 022 9
42 527 718 597 844 492 478 237 132 859 482 925 036 510 787 009 519 272 749 296 0
96 175
Found n-4,n-2,n+2,n+4 where n is 7 088 374 943 931 040 097 984 829 452 127 022 9
42 527 718 597 844 492 478 237 132 859 482 925 036 510 787 009 519 272 749 567 5
00 145
Found n-4,n-2,n+2,n+4 where n is 7 088 374 943 931 040 097 984 829 452 127 022 9
42 527 718 597 844 492 478 237 132 859 482 925 036 510 787 009 519 272 752 134 6
20 575
Found n-4,n-2,n+2,n+4 where n is 7 088 374 943 931 040 097 984 829 452 127 022 9
42 527 718 597 844 492 478 237 132 859 482 925 036 510 787 009 519 272 752 374 0
70 885
Found n-4,n-2,n+2,n+4 where n is 7 088 374 943 931 040 097 984 829 452 127 022 9
42 527 718 597 844 492 478 237 132 859 482 925 036 510 787 009 519 272 752 757 8
68 055
Found n-4,n-2,n+2,n+4 where n is 7 088 374 943 931 040 097 984 829 452 127 022 9
42 527 718 597 844 492 478 237 132 859 482 925 036 510 787 009 519 272 752 794 5
88 865
Found n-4,n-2,n+2,n+4 where n is 7 088 374 943 931 040 097 984 829 452 127 022 9
42 527 718 597 844 492 478 237 132 859 482 925 036 510 787 009 519 272 755 812 3
21 505
Total took 99388 ms
Press any key to continue . . .
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 14:09:25 | 显示全部楼层
原帖由 mathe 于 2008-2-14 14:02 发表
十进制计算我觉得应该慢一些,这也是为什么我要选择16进制计算。可以计算完了将计算结果再转化为10进制数。


一般情况下是这样的。
但 HugeCalc 内部充分利用了双进制内核的优势,当判定10^r ± d(d远小于10^r)素性时,内部会自动切换进10进制内核;否则就自动切换进16进制内核,而无论外部调用者究竟采用的是哪种内核。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 15:35:45 | 显示全部楼层
发现一个奇怪现象,对于随机开始的起始点,经常出来的结果要么没有,要么很多个,而不会出现只有一两个结果的情况。
挺奇怪,如果程序没有错误,看来四生素数的分布极其不均匀
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 16:07:35 | 显示全部楼层
耐着性子让计算机算了10次,每次得到结果数目如下:
4
0
0
11
8
7
4
0
5
5
感觉挺不平均
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 16:08:44 | 显示全部楼层
有没有计算过用HugeCalc判断一个100位数是不是素数平均需要花费多长时间?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 16:17:40 | 显示全部楼层
我觉得这个程序还有一处可以优化
假设TestPrimality(1)的调用比IsPrime()要快很多倍,
其实开始我们可以只对4个数都采用TestPrimality(1)来判断,如果全部返回true,然后再使用IsPrime()来判断。应该可以改善
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 16:32:29 | 显示全部楼层
IsPrime() 函数进行了及其严格的素性测试,比 TestPrimality(1) 肯定要费不少功夫,
但这是针对该数为素数的情形下;

由于“强伪素数”出现的概率很低,也就是说,如果一个数本身为合数,
即便调用 IsPrime() 函数,绝大部分都首先被 Miller-Rabin Test 给阻挡在外面了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 16:36:26 | 显示全部楼层
是这样,但是如果n-4是素数,n-2不是强伪素数(对于n-4是素数的大部分情况)
这种情况计算速度会有区别。
所以这个还是要看筛选后留下素数的比例有多高
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 16:45:15 | 显示全部楼层
这么一说,的确还可以提速不少。
毕竟要找的目标是稀有的,快速淘汰更显重要。
刚才我看待问题过于孤立了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 16:48:17 | 显示全部楼层
呵呵,实际试验结果发现这样好像更加慢,看来可能的原因是TestPrimality(1)成功率太低?不知道改成TestPrimality(5)是否会好一些。
我统计了一下,通常余下还有10万组数据需要检测。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-18 10:39 , Processed in 0.050711 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表