互いに素な確率(Sparkコードの練習)


自然数をランダムに2つ選んだとき,それらが互いに素である確率は \frac{6}{\pi^2} となるらしい.今回は分散処理フレームワーク「Spark」用の超初歩的なプログラムをかく練習も兼ねて,シミュレーションしてみた.

スポンサーリンク

互いに素となる確率

    \[ ゼータ関数 $\zeta (s) = \sum_{n=1}^{\infty}\frac{1}{n^s} \]

の特殊値 \zeta (2) = \pi^2/6 が関係している.感覚的な証明は非常にわかりやすい.

今回は証明・説明はせずに,コードと結果だけ載せる.Scala 言語ではなく,Spark 用の Java を採用.シミュレート時の(アルゴリズム的な)条件は以下の通り.

  • 自然数は (0,10000) からランダムに与える.
  • 100000 \times 100 組の自然数に対して判定.
  • 関数 {\rm gcd}(a,b) は再帰的に実装.

コードは以下の通り.

example が用意されている Monte Carlo のシミュレーションの丸パクリである.コンパイル後に気がついたが,これって自然数ではなくて非負整数なのでは(0 が選ばれた場合は互いに素ではないと判定されるので,一応セーフ…?)

 

実行結果


縦軸は時間 [ms],横軸は Slave 数.青は Partition 生成の時間,橙が Map-Reduce 処理にかかった時間.

予想以上に早くならない.Monte Carlo よりも分散効率が悪いらしい.

 

補足

Python でも検証.分散などは一切考えていない.こちらは gcd を再帰的ではなく繰り返し処理で定義した.

実行時間平均は 13.180999 [ms].PC もなにもかも違うので全く比較検証はできないが.

  • gcd の定義
  • list 構造の有無(Spark では処理の関係上先に 10000000 程度の配列を生成する)
  • PCの性能
  • そもそもこの程度の処理に Spark を持ち出す必要性がない
  • ランダム整数の範囲によっては素数の分布に偏りが見られる

上4つは計算時間,5つ目は円周率の近似に対する問題点.

このあたりをしっかり考えればもう少しまともな検証になるかもしれないが,今回はとりあえず Java + Spark のコンパイルが成功したのでよしとする.なお,値はどちらも 3.14 をよく近似していた.


スポンサーリンク