小数字最快的素数测试 [英] Fastest prime test for small-ish numbers
问题描述
我在业余时间玩着Euler项目，现在我需要进行一些重构.我已经安装了Miller-Rabin以及一些筛子.我以前曾听说过，筛网对于小批量的筛子实际上要快一些，例如不到几百万.有人对此有任何信息吗? Google并不是很有帮助.
I'm playing through project Euler in my spare time, and it's come to the point where I need to do some refactoring. I've implemented Miller-Rabin, as well as a few sieves. I've heard before that sieves are actually faster for small-ish numbers, as in under a few million. Does anybody have any information on this? Google wasn't very helpful.
推荐答案
是的，您会发现大多数算法都可以用空间交换时间.换句话说，通过允许使用更多的内存，大大提高了 * a 的速度.
Yes, you'll find with most algorithms that you can trade space for time. In other words, by allowing the use of more memory, the speed is greatly increased *a.
我实际上并没有知道 Miller-Rabin算法，但是，除非它比单个左移/累加和内存提取简单，否则它会被预先计算的筛子.
I don't actually know the Miller-Rabin algorithm but, unless it's simpler than a single shift-left/add and memory extraction, it will be blown out of the water by a pre-calculated sieve.
这里重要的事情是预先计算的.就性能而言，预先计算这样的事情是个好主意，因为前一百万个素数在不久的将来不太可能改变:-)
The important thing here is pre-calculated. It's a good idea, in terms of performance, to pre-calculate things like this since the first million primes will be unlikely to change in the near future :-)
换句话说，用以下内容创建筛子:
In other words, create your sieve with something like:
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++之类的内容传递给宏的常见警告.这为您提供了两全其美的优势，可以快速查找小"素数的表，而对于范围以外的那些则返回到一种计算方法.
with all the usual caveats about not passing things like a++ into macros. This gives you the best of both worlds, a blindingly fast table lookup for "small-ish" primes, dropping back to a calculation method for those outside the range.
很显然，您将使用其他方法之一编写程序来生成该查找表-您真的不需要手动输入所有内容.
Obviously you would write a program using one of the other methods to generate that lookup table - you don't really want to have to type it all in by hand.
但是，与所有优化问题一样，测量，不要猜测！
But, as with all optimisation questions, measure, don't guess!
* a 一个典型的例子是我曾经不得不为嵌入式系统编写的一些trig函数.这是一个具有竞争力的合同投标，并且系统的存储量比CPU占用的存储量还多.
*a A classic case of this was some trig functions I once had to write for an embedded system. This was a competitive contract bid and the system had a little more storage than CPU grunt.
我们实际上赢得了合同，因为我们功能的基准数字使竞争消失了.
We actually won the contract since our benchmark figures for the functions blew the competition away.
为什么?因为我们将这些值预先计算到了最初在另一台计算机上计算的查找表中.通过明智地使用归约(将输入值降低到90度以下)和触发属性(余弦只是正弦的相移，而其他三个象限与第一个象限相关的事实)，我们可以将查找表简化为180个条目(每半度一个).
Why? Because we pre-calculated the values into a lookup table originally calculated on another machine. By judicious use of reduction (bringing the input values down below 90 degrees) and trig properties (the fact that cosine is just a phase shift of sine and that the other three quadrants are related to the first), we got the lookup table down to 180 entries (one per half degree).
最好的解决方案是那些优雅的和 de回的:-)
The best solutions are those that are elegant and devious :-)
对于它的价值，以下C代码将为您生成这样一个表，所有小于400万(其中283,000个)的质数.
For what it's worth, the following C code will generate such a table for you, all the primes below four million (283,000 of them).
#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个素数).
If you can bump up the primeTbl table to sixteen million entries (16M), you'll find that's enough to keep the prime count above a million (the first 1,031,130 primes).
现在有一些方法可以减少存储空间，例如仅存储奇数并调整宏以解决这一问题，或者使用位掩码代替无符号字符.如果内存可用，我本人更喜欢算法的简单性.
Now there are ways to make that take less storage such as only storing odd numbers and adjusting the macro to take care of that, or using a bit mask instead of unsigned characters. I prefer simplicity of algorithms myself if the memory is available.
这篇关于小数字最快的素数测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
