primes - 校验大量的质数？ (用于验证)

是否存在用于计算数百万或数十亿质数的高质量校验和的巧妙算法？即具有最大的错误检测能力并且可能可细分？动机:通过使用小的位图筛选潜在因子(最大2 ^ 32-1)和使用第二个位图筛选中的数字，可以按需筛分大小最大为64位的小质数，每秒高达数百万。目标范围。算法和实现是相当简单和直接的，但是细节却是魔鬼:值往往会在各处推动或超过内置整数类型的限制，边界情况比比皆是(可以这么说)，甚至浮点严格性的差异都可能导致如果编程没有适当的防御力，则将其破坏。更不用说优化的编译器可能会产生的混乱，即使是在静态库中的已编译，已测试的代码上(如果使用了链接时代码生成)。更不用说更快的算法往往更复杂，因此更加脆弱。这有两个结果:测试结果基本上是没有意义的，除非使用最终的可执行镜像执行测试，并且非常需要在正常使用期间在运行时验证正确的操作。根据预先计算的值进行检查将获得最高的置信度，但是所需的文件又大又笨重。具有1000万个素数的文本文件的未压缩量约为100 MB，而压缩量则超过10 MB。存储字节编码的差异时，每个素数需要一个字节，并且熵编码最多可以将大小减小一半(对于1000万个素数，则为5 MB)。因此，即使仅覆盖2 ^ 32的小因素的文件也将占用大约100 MB的空间，并且解码器的复杂性将超过窗口筛本身的复杂性。这意味着对文件的检查是不可行的，除非作为对新建可执行文件的最终发行检查。更不用说值得信赖的文件不容易获得。 Prime Pages提供了前5000万个素数的文件，即使是惊人的primos.mat.br也只能达到1,000,000,000,000。这是不幸的，因为许多边界情况(==需要测试)发生在2 ^ 62和2 ^ 64-1之间。剩下校验和。这样，空间需求将是有限的，并且仅与测试用例的数量成比例。我不想要求像MD5或SHA-256这样的体面校验和可用，并且目标数字都是素数时，应该可以对数字进行一些简单的操作来生成高质量，高分辨率的校验和他们自己。到目前为止，这是我想出的。原始摘要由四个64位数字组成。最后，可以将其折叠成所需的尺寸。 for (unsigned i = 0; i < ELEMENTS(primes); ++i) { digest[0] *= primes[i]; // running product (must be initialised to 1) digest[1] += digest[0]; // sum of sequence of running products digest[2] += primes[i]; // running sum digest[3] += digest[2] * primes[i]; // Hornerish sum }每个素数有两个(不相关)muls，速度足够不错，并且除了简单的总和之外，每个组件始终发现了我尝试通过摘要进行的所有错误。但是，我不是数学家，经验测试也不是有效性的保证。是否有一些数学属性可用于设计—而不是像我那样“做饭” —明智，可靠的校验和？是否有可能以一种可逐步实现的方式设计校验和，在某种意义上说，可以分别处理子范围，然后将结果与一点算术结合起来，就可以得出相同的结果，就好像整个范围都经过了一次校验和一样？如今，与所有高级CRC实现相同的东西倾向于启用并行处理。 EDIT 当前方案的基本原理是:计数，总和和乘积不取决于素数添加到摘要中的顺序。它们可以在单独的块上计算然后组合。校验和确实取决于顺序。那就是它的存在理由。但是，如果可以以某种方式组合两个连续块的两个校验和以给出组合块的校验和，那就太好了。有时可以根据外部源(例如oeis.org上的某些序列)或诸如primos.mat.br上的一千万个素数的批次(索引给出第一个和最后一个素数，隐含数字== 1000万)来验证计数和总和。但是，产品和校验和没有运气。在我花大量时间和计算能力来进行摘要的计算和验证时，摘要涵盖了直到2 ^ 64的所有小因素，我想听听专家对此的看法...我目前正在32位和64位版本中测试驱动的方案如下所示: template<typename word_t>struct digest_t{ word_t count; word_t sum; word_t product; word_t checksum; // ... void add_prime (word_t n) { count += 1; sum += n; product *= n; checksum += n * sum + product; }};这样做的好处是，32位摘要组成部分等于相应64位值的下半部分，这意味着即使需要快速的32位验证，也只需要计算存储64位摘要。可以在此简单的sieve test program @ pastebin中找到摘要的32位版本，以进行动手实验。可以在a sieve that works up to 2^64-1的较新粘贴中找到经过修订的模板版本的完整Monty。 最佳答案 我已经做了很多工作来并行化Cell体系结构上的操作。这有相似的感觉。在这种情况下，我将使用快速且可能是增量的哈希函数(例如xxHash或MurmurHash3)和hash list(这是Merkle Tree的灵活性较差的专业化)。这些哈希值非常快。通过一些简单的操作很难变得更好。哈希列表提供了并行性-列表的不同块可以由不同的线程处理，然后对哈希进行哈希处理。您也可以使用Merkle树，但我怀疑这会变得更加复杂而没有太多好处。实际上将范围划分为对齐的块-我们将其称为微块。 (例如，微区块的范围为[n 要处理微块，请计算您需要计算的内容，将其添加到缓冲区中，然后对缓冲区进行哈希处理。 (增量散列函数将提供较小的缓冲区。不必每次都用相同长度的数据填充缓冲区。)每个微块哈希将放置在circular buffer中。 将循环缓冲区划分为可散列的块(“宏块”)。当这些宏块可用时，或者如果没有更多的微块，则以适当的顺序递增散列。 生成的哈希是您想要的哈希。 一些附加说明:我建议一种设计，其中线程保留循环缓冲区有空间的待处理微块的范围，对其进行处理，将值转储到循环缓冲区中，然后重复执行。 这有一个额外的好处，您可以决定要动态使用多少个线程。例如当请求新范围的微块时，每个线程都可以检测是否有太多/很少的线程在运行并进行调整。 我个人将使最后一个微块哈希添加到宏块的线程清理该宏块。较少的参数可以通过这种方式进行调整。 维护循环缓冲区并不像听起来那么难-仍未处理的最低阶宏块定义了循环缓冲区代表“宏块空间”的哪一部分。您所需要的只是一个简单的计数器，该计数器在适当时表示此增量。 的另一个好处是，由于线程会定期执行预留/工作/预留/工作周期，因此线程出乎意料的缓慢不会对运行时间造成同样严重的影响。 如果您希望使某些东西不那么健壮但更容易，可以使用“条纹”模式放弃很多工作-确定最大线程数(N)，并使每个线程每N个处理一次-th个微块(由其线程“ID”偏移)，然后对每个线程散列结果宏块。然后，最后，从N个线程哈希宏块哈希。如果线程数少于N，则可以将工作分配给所需的线程数。 (例如64个最大线程，但三个实线程，线程0处理21个虚拟线程，线程1处理21个虚拟线程，线程2处理22个虚拟线程-不理想，但并不可怕)这本质上是一棵浅默克尔树，而不是哈希列表。关于primes - 校验大量的质数？ (用于验证)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26606355/