乱数アルゴリズム
計算における乱数の利用は、従来、数値積分の分野で用いられてきた。
数値積分におけるモンテカルロ法：$\pi$の計算
最近、乱数を利用した確率的(乱択)アルゴリズムの理論が発展した
乱択アルゴリズムには2種類ある。ともに、乱数を利用して、正答を高確率で返すが、
１．モンテカルロ法は、常に答を返すが、間違うこともある。
２．ラスベガス法は、答えを返さないこともあるが、誤答を返すことはない。
ラスベガス法で、一定時間後に必ず答を返すようにすれば、モンテカルロ法になる。
乱数の生成法
真の乱数：決定的に動作するコンピュータでは生成できない！定義さえ難しい
疑似乱数生成法
線型合同法：定数$a,b,m$を使って、疑似乱数列$r_n$を次の式で作る$r_{n+1}=ar_n+b \mod m$
線型合同法の欠点
- 最大周期が$m$
- 下位ビットに規則性がある
- よって $m$ を十分大きくしなければならない
新しい疑似乱数生成法
Mersenne Twister、
xorshift
パズル．周期 $m=4096, 65536$ のとき乱数分布はどうなるか。
数値積分：$k$桁目までを求めるモンテカルロ法
乱数を利用して、(多重)定積分を計算する手法を総称してモンテカルロ法という
例：単位円の面積、すなわち円周率を求める
πの計算
第1象限中の単位正方形上に $n$ 個の点をランダムにばらまき、その点が単位円に含まれれば赤で、含まれなければ青で表示。点が単位円に含まれる確率は4分円の面積を近似するから、それを4倍して$\pi$の近似値とする。
±の後の値は標準誤差であり、$\sqrt{n}$に反比例するので、信頼できる精度を1桁あげたければ、点の数$n$を100倍にする必要があり、計算時間は当然$n$に比例する。
モンテカルロ法による積分では、コンピュータ(言語)が標準で提供する擬似乱数よりも、無理数の1倍, 2倍, 3倍, ･･･の小数部分を値とする準乱数のほうが精度がよい。
パズル．上のπの計算アプリで、以下の実験を行え。
- 点の数 n=1,000,000 のときのπの値および計算時間を疑似乱数の場合と準乱数の場合で比較せよ。
- 疑似乱数でn=2,000,000 4,000,000 のときの精度と計算時間を比較し、n=100,000,000 のときの精度と計算時間を予測せよ。
確率的素数判定法（モンテカルロ法）
フェルマーテスト：以下の非素数判定を繰り返しすり抜けることをもって、確率的素数判定を行う
フェルマーの小定理の対偶
$n$ と互いに素な整数 $a$ が ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$
を満たせば、$n$ は素数でない。
フェルマーテストのアルゴリズム
以下 1.～3. を適当な回数($r$ 回)繰りかえす
- $2$ 以上 $n$ 未満の自然数 $a$ をランダムに選ぶ。
- $a$ と $n$ の公約数が $1$ でなければ、「$n$は合成数」と出力して終了
- ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$ ならば、「$n$は合成数」と出力して終了
「$n$は確率的素数」と出力して終了
フェルマーテストは、ユークリッドの互除法（公約数の計算）やBinary法（べき乗計算）を用いて高速に計算できる。
フェルマーテストが「合成数」と出力したとき、$n$ は実際に合成数である。
「確率的素数」と出力したとき、$n$ は実際に素数であるとは限らないが、
十分回数繰りかえせば、高い確率で素数である。
しかし・・・
フェルマーテストは完全な素数判定法ではない
カーマイケル数（
絶対擬素数）は合成数である
にもかかわらず、自身と互いに素な任意の $a$ に対して ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$
なので、「確率的素数」と判定されてしまうことがある。
パズル．カーマイケル数 $46657$ が $r=10$ のフェルマーテストをすり抜け、「確率的素数」とされる確率を求めよ。
ヒント．カーマイケル数 $n$ が「合成数」と判定されないのは選んだ $a$ との公約数が 1 のときなので、$46657=13\times 37\times 97$ が $r=1$ のフェルマーテストをすり抜け、「確率的素数」とされる確率は $\displaystyle \frac{12\times 36\times 96-1}{46657-1}$ である。
フェルマーテストを改善した、
ミラー-ラビン素数判定法がある。
また最近、決定的多項式時間で動作する
AKS素数判定法も開発された。
ラスベガス法
高確率で正答を返し、間違うことはないが、
低確率で、答えが得られない
例．確率的クイックソート：データ数 $n$、$c$ は適当な定数
・分割基準値をランダムに選んで計算
・$cn\log n$ 時間後に終了していなければ強制的に終了
クイックソートは
多くの入力に対する計算時間は$n\log n$に比例するが
最悪の入力に対する計算時間は$n^2$に比例する。
確率的クイックソートは
すべての入力に対して計算時間は$n\log n$に比例するが
答えを返さないことがありうる
パズル．クイックソートのモンテルカルロアルゴリズムを述べよ。
終了ページ
終了ページ
終了ページ
終了ページ