我在闲暇时间玩Euler项目,而且我需要做一些重构.我已经实施了Miller-Rabin以及一些筛子.我之前听说过,对于小数字来说,筛子实际上更快,就像几百万以下一样.有没有人有这方面的信息？谷歌不是很有帮助.
是的,您可以找到大多数算法,您可以随时交换空间.换句话说,通过允许使用更多内存,速度大大提高*a.
我实际上并不知道 Miller-Rabin算法,但是,除非它比单个左移/添加和记忆提取更简单,否则它将通过预先计算的筛子从水中吹出.
这里重要的是预先计算.在性能方面,预先计算这样的事情是一个好主意,因为在不久的将来,第一批百万次素数将不太可能改变:-)
换句话说,用以下内容创建筛子:
unsigned char primeTbl[] = {0,0,1,1,0,1,0,1,0,0,0,1};
#define isPrime(x) ((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))
关于不将事物传递a++到宏中的所有常见警告.这为您提供了两全其美的优势,一个快速查找"小型"素数的表,并回退到范围之外的计算方法.
显然你会使用其他方法编写一个程序来生成查找表 - 你真的不想手动输入它.
但是,与所有优化问题一样,测量,不要猜!
*a一个典型的例子是我曾经为嵌入式系统编写的一些trig函数.这是一个有竞争力的合同竞标,系统有比CPU咕噜声更多的存储空间.
我们实际上赢得了合同,因为我们的功能基准数据引发了竞争.
为什么？因为我们将值预先计算到最初在另一台机器上计算的查找表中.通过明智地使用缩减(将输入值降低到90度以下)和触发属性(余弦只是正弦的相移以及其他三个象限与第一个相关的事实),我们将查找表缩小到180个条目(每半度一个).
最好的解决方案是优雅和狡猾的解决方案:-)
对于它的价值,以下C代码将为您生成这样一个表,所有素数低于四百万(其中283,000).
#include <stdio.h>
static unsigned char primeTbl[4000000];
int main (void) {
int i, j;
for (i = 0; i < sizeof(primeTbl); i++)
primeTbl[i] = 1;
primeTbl[0] = 0;
primeTbl[1] = 0;
for (i = 2; i < sizeof(primeTbl); i++)
if (primeTbl[i])
for (j = i + i; j < sizeof(primeTbl); j += i)
primeTbl[j] = 0;
printf ("static unsigned char primeTbl[] = {");
for (i = 0; i < sizeof(primeTbl); i++) {
if ((i % 50) == 0) {
printf ("\n ");
}
printf ("%d,", primeTbl[i]);
}
printf ("\n};\n");
printf ("#define isPrime(x) "
"((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))\n");
return 0;
}
如果你可以将primeTbl表格提升到1600万个条目(16M),你会发现这足以让黄金数量保持在一百万以上(前1,031,130个素数).
现在有办法让那个拿更少的存储空间,例如存储仅奇数和调整宏采取照顾,或使用位掩码,而不是无符号的字符.如果内存可用,我更喜欢简单的算法.
我建议采用分层方法.首先,确保没有小的素因子.通过前20或30个素数进行试验分割,但如果使用巧妙的方法,则可以减少使用gcds所需的分割数量.此步骤过滤掉约90%的复合材料.
接下来,测试该数字是否是基于2的强可能质数(米勒 - 拉宾测试).该步骤除去几乎所有剩余的复合物,但是一些稀有复合物可以通过.
最后的证明步骤取决于你想要的大小.如果您愿意在小范围内工作,请在2-pseudoprimes列表上进行二进制搜索,使其达到您允许的最大值.如果那是2 ^ 32,那么您的列表将只有10,403个成员,因此查找应该只需要14个查询.
如果你想要达到2 ^ 64,那么现在就足以检查这个数字是否是BPSW伪赝假人(感谢Jan Feitisma的工作).(你也可以下载所有例外的3 GB列表,删除试验部门将删除的那些,并编写基于磁盘的二进制搜索.) TR很好地有一个很好的页面解释如何合理有效地实现它.
如果需要更高,请实现上述方法并将其用作Pocklington样式测试的子例程.这延伸了"小小"的定义; 如果您想了解有关这些方法的更多信息,请询问.