不要な繰り返しをカットするために、Sundaramアルゴリズムのふるいを少し変更しましたが、非常に高速に見えます。
このアルゴリズムは、このトピックで最も受け入れられている@Ted Hopp のソリューションよりも実際には 2 倍高速です。0 ～ 1M の間の 78498 個の素数を解くには、Chrome 55 では 20 ～ 25 ミリ秒、FF 50.1 では < 90 ミリ秒かかります。また、@vitaly-t の get next prime アルゴリズムは興味深いように見えますが、結果ははるかに遅くなります。
これがコアアルゴリズムです。セグメンテーションとスレッド化を適用して、優れた結果を得ることができます。
"use strict";
function primeSieve(n){
var a = Array(n = n/2),
t = (Math.sqrt(4+8*n)-2)/4,
u = 0,
r = [];
for(var i = 1; i <= t; i++){
u = (n-i)/(1+2*i);
for(var j = i; j <= u; j++) a[i + j + 2*i*j] = true;
}
for(var i = 0; i<= n; i++) !a[i] && r.push(i*2+1);
return r;
}
var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);
ループ制限の説明:
エラストテネスのふるいと同様に、スンダラムのふるいアルゴリズムも、リストから選択されたいくつかの整数を取り消します。取り消し線を引く整数を選択するには、ルールは i + j + 2ij ≤ n です。ここで、i と j は 2 つのインデックスで、n は要素の合計数です。すべての i + j + 2ij に取り消し線を引くと、残りの数が 2 倍されて奇数化 (2n+1) され、素数のリストが表示されます。最終段階は、実際には偶数の自動割引です。その証拠はここで美しく説明されています。
Sundaram のふるいは、ループ インデックスの開始と終了の制限が正しく選択され、非素数の冗長な (複数の) 削除がまったく (または最小限に) 行われない場合にのみ高速になります。取り消し線を引く数字を計算するには i と j の値が必要なので、i + j + 2ij から n までどのようにアプローチできるか見てみましょう。
i)したがって、i と j が等しい場合に取り得る最大値を見つける必要があります。これは 2i + 2i^2 = n です。二次方程式を使用して i の正の値を簡単に解くことができます。t = (Math.sqrt(4+8*n)-2)/4,
j)内側のループ インデックス j は、i から開始し、現在の i 値で移動できるポイントまで実行する必要があります。それ以上はありません。i + j + 2ij = n であることがわかっているので、これは次のように簡単に計算できます。u = (n-i)/(1+2*i);
これにより、冗長な交差が完全に除去されるわけではありませんが、冗長性が「大幅に」除去されます。たとえば、n = 50 の場合 (100 までの素数をチェックするため)、50 x 50 = 2500 を実行する代わりに、合計で 30 回の反復のみを実行します。明らかに、このアルゴリズムは O(n^2) 時間の複雑さと見なされるべきではありません。
i j v
1 1 4
1 2 7
1 3 10
1 4 13
1 5 16
1 6 19
1 7 22 <<
1 8 25
1 9 28
1 10 31 <<
1 11 34
1 12 37 <<
1 13 40 <<
1 14 43
1 15 46
1 16 49 <<
2 2 12
2 3 17
2 4 22 << dupe #1
2 5 27
2 6 32
2 7 37 << dupe #2
2 8 42
2 9 47
3 3 24
3 4 31 << dupe #3
3 5 38
3 6 45
4 4 40 << dupe #4
4 5 49 << dupe #5
その中で重複は 5 つだけです。22、31、37、40、49. n = 100 の場合、冗長性は約 20% ですが、n = 10M の場合は約 300% に増加します。これは、SoS をさらに最適化することで、n が大きくなるにつれてさらに速く結果を取得できる可能性を秘めていることを意味します。したがって、1 つのアイデアはセグメンテーションであり、n を常に小さく保つことです。
OK..このクエストをもう少し進めてみることにしました。
i === 1繰り返される交差を注意深く調べた後、場合を除いて、iまたはjインデックス値のいずれかまたは両方が 4、7、10、13、16、19.. の間にあるという事実に気づきました。 . シリーズ、重複交差が生成されます。そして、内側のループを の時だけ回すことi%3-1 !== 0で、さらに全ループ数の 35 ～ 40% 程度の削減を実現。たとえば、1M 整数の場合、ネストされたループの合計ターン数は 1.4M から 1M に減少しました。わお..！ここではほとんど O(n) について話しています。
私はちょうどテストをしました。JS では、1B までカウントする空のループだけで 4000 ミリ秒かかります。以下の修正されたアルゴリズムでは、100M までの素数を見つけるのに同じ時間がかかります。
また、このアルゴリズムのセグメンテーション部分を実装して、ワーカーにプッシュしました。そのため、複数のスレッドも使用できるようになります。しかし、そのコードは少し後で続きます。
では、修正されたスンダラムのふるいをご紹介しましょう。Chrome V8 と Edge ChakraCore を使用して、約 15 ～ 20 ミリ秒で 0 ～ 1M の素数を計算します。
"use strict";
function primeSieve(n){
var a = Array(n = n/2),
t = (Math.sqrt(4+8*n)-2)/4,
u = 0,
r = [];
for(var i = 1; i < (n-1)/3; i++) a[1+3*i] = true;
for(var i = 2; i <= t; i++){
u = (n-i)/(1+2*i);
if (i%3-1) for(var j = i; j < u; j++) a[i + j + 2*i*j] = true;
}
for(var i = 0; i< n; i++) !a[i] && r.push(i*2+1);
return r;
}
var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);
ええと...最後に、インターネット上で見つけることができた最速のJavaScriptふるいになるように、ふるい(独創的なスンダラムのふるいに由来する)を実装したと思います。 「アトキンスのふるい」。また、これは Web ワーカー、マルチスレッドにも対応しています。
このように考えてください。この控えめな AMD PC では、シングル スレッドで JS が 10^9 までカウントするのに 3,300 ミリ秒かかります。次の最適化されたセグメント化された SoS では、14,000 ミリ秒で 50847534 素数が 10^9 まで計算されます。これは、カウントするだけの 4.25 倍の操作を意味します。印象的だと思います。
自分でテストできます。
console.time("tare");
for (var i = 0; i < 1000000000; i++);
console.timeEnd("tare");
そしてここで、最高のセグメント化された Sundaram の Seieve を紹介します。
"use strict";
function findPrimes(n){
function primeSieve(g,o,r){
var t = (Math.sqrt(4+8*(g+o))-2)/4,
e = 0,
s = 0;
ar.fill(true);
if (o) {
for(var i = Math.ceil((o-1)/3); i < (g+o-1)/3; i++) ar[1+3*i-o] = false;
for(var i = 2; i < t; i++){
s = Math.ceil((o-i)/(1+2*i));
e = (g+o-i)/(1+2*i);
if (i%3-1) for(var j = s; j < e; j++) ar[i + j + 2*i*j-o] = false;
}
} else {
for(var i = 1; i < (g-1)/3; i++) ar[1+3*i] = false;
for(var i = 2; i < t; i++){
e = (g-i)/(1+2*i);
if (i%3-1) for(var j = i; j < e; j++) ar[i + j + 2*i*j] = false;
}
}
for(var i = 0; i < g; i++) ar[i] && r.push((i+o)*2+1);
return r;
}
var cs = n <= 1e6 ? 7500
: n <= 1e7 ? 60000
: 100000, // chunk size
cc = ~~(n/cs), // chunk count
xs = n % cs, // excess after last chunk
ar = Array(cs/2), // array used as map
result = [];
for(var i = 0; i < cc; i++) result = primeSieve(cs/2,i*cs/2,result);
result = xs ? primeSieve(xs/2,cc*cs/2,result) : result;
result[0] *=2;
return result;
}
var primes = [];
console.time("primes");
primes = findPrimes(1000000000);
console.timeEnd("primes");
console.log(primes.length);
これよりも良くなるかどうかはわかりません。ご意見をお待ちしております。