モンテカルロ法で次元の呪いを体験する - ぷる日記
MCMC講義（伊庭幸人） 難易度 - YouTube を観ていたところ、「(モンテカルロ法で円周率を求めるのは高次元になるとうまく行かなくなるので)一度は必ずやってみるべし！」と言われたのでやってみました。(4:17～) もちろんSASで。 N次元単位超球の(超)体積 超球を包む1辺の長さが2の超立方体の(超)体積 円周率を求める コードをシンプルにするために球の中心を原点にとり、すべての次元に対して正の方向のみを考えます。すると、球内部の体積は、単位立方体の体積はとなります。 この立方体の中に一様ランダムに点を打っていったときに、点を打った数と球の中に点が入ったときの数の比率が立方体の体積に対する球内部の体積の比率に近くなることが期待できます。 式で書くと、 について整理すると となります。*1 コード %macro pi(dim=, rep=); data pi; do i = 1 t
よしいずの雑記帳 Pollardのロー法による因数分解プログラムの例
Rubyによる、Pollardのロー法を用いた因数分解プログラムの例。 Pollardのロー法とは 与えられた自然数の因数を求めるアルゴリズムのうち、乱数を用いた発見的な方法はモンテカルロ法と呼ばれる。Pollard(ポラード)のロー法は、モンテカルロ法の一種である。 Pollardのロー法は、有限集合 S から S 自身への乱数関数 f によって定まる乱数列 s, f(s), f(f(s)), ... を利用する。ただし、最初の s は S の中からランダムに一つ選ぶ。この数列は、どこかで同じ値が現れ(∵部屋割り論法)、その後は同じ数の並びが周期的に繰り返される。その様子がギリシャ文字のρ(ロー)に似ていることから、ロー法と名づけられた(らしい)。 アイデアを大雑把に説明すれば、n を自然数、p を n の最小の素因数とし、f(x) = x^2 + 1 mod p、F(x) = x^2
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
