モンテカルロ法を使って、円周の直径に対する比率である定数 Pi を推量します。
次元 N x N の正方形があるとしましょう。 この N は比較的大きな自然数 (例えば 1000) で、半径 1 の円盤がこの正方形に入っているとします。 N*N、つまり N の平方に N2 という名前をつけます。 この正方形の内側の点をランダムに選択すると、 その点が円盤に当たる確率は Pi/N2 です。
定数 Pi を推量する方法は次のようなものです。 自然数 K が与えられたとき、その正方形の内側にある K 個の点をランダムに、K 回選択します。 それぞれの回において、きっちり1度だけ点を選びます。 前回選んだ点を中心とする円盤に k 回目に選択した点が当っていたら、1度当ったことを記録します。 k 回目における記録された当った回数は、直前の回までに k-1 点選んだとき、(k-1)*Pi/N2 であることが期待できます。 そのため、K 回試行して当った合計回数は、理想的には (K*(K-1)/2)*Pi/N2 であることになります。 もし K が N2 に到達すれば、期待される当った合計回数は (N2-1)*Pi/2 になります。 N が無限大に近付くと、当った合計回数を N2 で割った数が Pi/2 に収束することが証明できます。
もし上記の試行を与えられた説明の通りに実装してしまうと、 その実装の時間効率は、k が 1 から N2 までの範囲を取るとき k 回目にかかる時間が k に比例するので、 明らかに N2*N2 に比例してしまいます。 1000 のオーダーの N を取り扱うことを考えると (つまり N2 は 1,000,000 のオーダーになります)、 そのような実装は実用的ではありません。 この問題に対処するために、この正方形に N2 ユニットの正方形に分割するグリッド (次元は 1 x 1 です) を導入します。 それからそれぞれのユニット正方形とその内側にある選んだ点のリストを関連させます。 それぞれの回において、まず元の正方形の内側からランダムに点を選択します; 次にこの点を含むユニット正方形を見つけます; その後、当該ユニット正方形もしくは隣接するユニット正方形に関連するリストを探索して、 この回で選択した点によって生成された当った回数を数えます。 これらのリスト中に存在しない点を中心とする円盤をこの点が当たることはありません。 それぞれのユニット正方形は最大8つの隣接するユニット正方形を取ることができ、 試行最中におけるそれぞれの正方形に関連するリストの平均の長さは 1 未満なので、 それぞれの回にかかる時間は O(1) つまり定数に抑えられます。 それゆえ全体の試行にかかる時間は O(N2) になります。
上記に示した実装とテストのための追加コードは オンライン から得られます。