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

mathe

呵呵，好像也看不出明显的速度区别。 看我这次运行结果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 . . .

gxqcn

原帖由 mathe 于 2008-2-14 14:02 发表 十进制计算我觉得应该慢一些，这也是为什么我要选择16进制计算。可以计算完了将计算结果再转化为10进制数。

一般情况下是这样的。 但 HugeCalc 内部充分利用了双进制内核的优势，当判定10^r ± d(d远小于10^r)素性时，内部会自动切换进10进制内核；否则就自动切换进16进制内核，而无论外部调用者究竟采用的是哪种内核。

mathe

发现一个奇怪现象，对于随机开始的起始点，经常出来的结果要么没有，要么很多个，而不会出现只有一两个结果的情况。 挺奇怪，如果程序没有错误，看来四生素数的分布极其不均匀

mathe

耐着性子让计算机算了10次，每次得到结果数目如下： 4 0 0 11 8 7 4 0 5 5 感觉挺不平均

mathe

有没有计算过用HugeCalc判断一个100位数是不是素数平均需要花费多长时间？

mathe

我觉得这个程序还有一处可以优化 假设TestPrimality(1)的调用比IsPrime()要快很多倍， 其实开始我们可以只对4个数都采用TestPrimality(1)来判断，如果全部返回true,然后再使用IsPrime()来判断。应该可以改善

gxqcn

IsPrime() 函数进行了及其严格的素性测试，比 TestPrimality(1) 肯定要费不少功夫， 但这是针对该数为素数的情形下； 由于“强伪素数”出现的概率很低，也就是说，如果一个数本身为合数， 即便调用 IsPrime() 函数，绝大部分都首先被 Miller-Rabin Test 给阻挡在外面了。

mathe

是这样，但是如果n-4是素数，n-2不是强伪素数（对于n-4是素数的大部分情况） 这种情况计算速度会有区别。 所以这个还是要看筛选后留下素数的比例有多高

gxqcn

这么一说，的确还可以提速不少。 毕竟要找的目标是稀有的，快速淘汰更显重要。 刚才我看待问题过于孤立了。

mathe

呵呵，实际试验结果发现这样好像更加慢，看来可能的原因是TestPrimality(1)成功率太低？不知道改成TestPrimality(5)是否会好一些。 我统计了一下，通常余下还有10万组数据需要检测。