7

我在业余时间玩了 Euler 项目，到了需要进行一些重构的地步。我已经实现了 Miller-Rabin，以及一些筛子。我之前听说过筛子实际上对于较小的数字更快，例如在几百万以下。有人有这方面的信息吗？谷歌不是很有帮助。

4

4 回答 4

10

是的，你会发现大多数算法都可以用空间换时间。换句话说，通过允许使用更多内存，速度大大提高*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一个经典案例是我曾经为嵌入式系统编写的一些三角函数。这是一个有竞争力的合同投标，而且系统的存储空间比 CPU 多一点。

我们实际上赢得了合同，因为我们的功能基准数据击败了竞争对手。

为什么？因为我们将这些值预先计算到了最初在另一台机器上计算的查找表中。通过明智地使用归约（将输入值降低到 90 度以下）和触发属性（余弦只是正弦的相移并且其他三个象限与第一个象限相关的事实），我们将查找表降低到180 个条目（每半度一个）。

最好的解决方案是那些优雅而狡猾的:-)

对于它的价值，下面的 C 代码将为您生成这样一个表，所有低于 400 万的素数（其中 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)，您会发现这足以将素数保持在 100 万以上（前 1,031,130 个素数）。

现在有一些方法可以减少存储空间，例如只存储奇数并调整宏来处理它，或者使用位掩码而不是无符号字符。如果内存可用，我自己更喜欢算法的简单性。

于 2010-09-20T21:59:02.697 回答
6

我建议采用分层方法。首先，确保没有小的质因数。前 20 或 30 个素数的试除法是可行的，但如果您使用巧妙的方法，您可以使用 gcd 减少所需的除法次数。这一步过滤掉了大约 90% 的复合材料。

接下来，测试该数字是否为以 2 为底的强可能素数（Miller-Rabin 检验）。此步骤几乎去除了所有剩余的复合材料，但一些罕见的复合材料可以通过。

最后的证明步骤取决于你想去多大。如果您愿意在小范围内工作，请在 2-pseudoprimes 列表上进行二进制搜索，直到您允许的最大范围内。如果是 2^32，那么您的列表将只有 10,403 个成员，因此查找应该只需要 14 个查询。

如果您想上升到 2^64，现在（感谢Jan Feitisma的工作）检查该数字是否为 BPSW 伪素数就足够了。（您还可以下载 3 GB 的所有异常列表，删除试用部门将删除的那些，然后编写基于磁盘的二进制搜索。） TR Nicely有一个很好的页面，解释了如何合理有效地实现这一点。

如果您需要更高，请实现上述方法并将其用作 Pocklington 式测试的子程序。这延伸了“small-ish”的定义；如果您想了解有关这些方法的更多信息，请询问。

于 2010-09-21T18:32:47.577 回答
2

作为预计算概念的变体，您可以首先廉价地检查候选数p是否可被 2、3、5、7 或 11 整除。如果不是，则声明p质数 if 2 p-1 = 1 (mod p ）。这在某些时候会失败，但它的工作量高达 1 亿，因为我对其进行了测试（预计算）。

换句话说，所有以 2 为底的小费马伪素数都可以被 3、5、7 或 11 之一整除。

编辑：

正如@starblue 正确指出的那样，以上内容是完全错误的。我的程序中有一个错误。我能做的最好的是将以上内容修改为：

如果候选p能被 2、3、5、7 或 11 整除，则声明它是合数；
否则，如果p是 {4181921, 4469471, 5256091, 9006401, 9863461} 之一，则声明为复合；
否则，如果p通过了基数 2 和 5 的 Miller-Rabin 检验，则声明它是素数；
否则声明它是复合的。

我测试了小于 10,000,000 的整数。也许一对不同的碱基会做得更好。

请接受我为我的错误道歉。

编辑2：

好吧，我所追求的信息似乎已经在米勒拉宾算法的维基百科页面上，标题为“测试的确定性变体”的部分。

于 2010-09-21T00:20:15.053 回答
1

唯一的方法是对自己进行基准测试。当你这样做的时候，把它写下来，然后在网上的某个地方发布。

于 2010-09-20T21:54:52.843 回答