14

素数の生成は、特に新しいプログラミング言語、プラットフォーム、またはスタイルを試すときに、私が時々試みるおもちゃの問題です。

Hadoop (Map Reduce) を使用して、素数生成アルゴリズムまたは素数テスト アルゴリズムを作成しようと考えていました。

この質問を投稿して、ヒント、参考文献、アルゴリズム、アプローチを取得すると思いました。

私の主な関心は Map Reduce ベースのアルゴリズムですが、新しい Hadoop プログラミング モデルや、たとえばPiCloudの使用を検討してもかまいません。

ここで、素数生成に関するいくつかの興味深い質問があるようです: here、here、およびhere ですが、並列アプローチに関連するものは何もありませんでした。

前もって感謝します。

4

1 に答える 1

14

これは、マッピングと削減 (折りたたみ) に基づいて構築されたアルゴリズムです。エラトステネスのふるいを表現

     P = {3,5,7, ...} \ U {{ p 2 , p 2 +2p, p 2 +4p, ...} | p in P }

素数が奇数の場合 (つまり、2 がない場合)。折りたたみツリーは、次のように、右に無限に深くなります。

ここに画像の説明を入力

ここで、各素数は、その素数の奇数倍数のストリームをマークします。たとえば、7 : 49、49+14、49+28、 ... の場合、これらはすべてマージされてすべての合成数が得られ、素数は合成数の間のギャップ。これは Haskell にあるため、タイミングは遅延評価メカニズムによって暗黙的に処理されます (また、各比較ノードが右からの数を要求することなく常に左からの最初の数を通過させるというアルゴリズム調整。とにかく大きい）。

倍数生成のシードとして奇素数の代わりにオッズを使用して、物事を単純化することができます (明らかなパフォーマンスへの影響があります)。

仕事は、連続する素数の正方形の間のセグメントに自然に分割できます。Haskell コードが続きますが、これも実行可能な疑似コードと見なすことができます(:はリスト ノードの遅延コンストラクターであり、関数呼び出しf(x)が記述されf x、括弧はグループ化にのみ使用されます)。

primes = 2 : g []
  where
    g ps = 3 : minus [5,7..] (_U [[p*p, p*p+2*p..] | p <- g ps])
    _U ((x:xs):t) = x : union xs (_U (pairs t))
    pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t

union (x:xs) (y:ys) = case compare x y of 
    LT -> x : union  xs (y:ys) 
    EQ -> x : union  xs    ys 
    GT -> y : union (x:xs) ys

minus (x:xs) (y:ys) = case compare x y of
    LT -> x : minus  xs (y:ys) 
    EQ ->     minus  xs    ys 
    GT ->     minus (x:xs) ys

議論はここにあります。より洗練された遅延スケジューリングはこちらです。また、このSOの回答は、（関連する）Haskellコードのジェネレーターに関するおおよその翻訳を示しています。これはPythonで。

于 2012-09-24T11:10:01.390 に答える