このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • 疑似乱数 へ行く。

*擬似乱数 [#p09a88d6]

-="pseudo-randam"
-(有限状態数の計算機を使って生成する限り)再現性のある擬似乱数列は必ず周期的になる。
--計算機が有限状態しか持たないと、生成する数がいつかは過去に生成したときと同じ状態になる。その後生成される数列も同じになる。つまり、周期が存在する。
-計算機科学全体ではあまり明確な定義がないらしいが、暗号理論の分野では明確な定義がある。
--数列が与えられて、多項式時間ではその数列と真の乱数列の区別が付かなければ、擬似乱数と呼ばれる。

*擬似乱数の必要性 [#x231f5b3]

-シミュレーション
--同じ実験を繰り返すために再現性が必要。
-暗号技術

*擬似乱数生成関数が上限値を持っているときに、それより大きい擬似乱数を作る場合の注意 [#x0a16c05]

 擬似乱数生成関数の出力値である複数の擬似乱数を足し算したり、掛け算してはいけません。なぜならばこうして得た値は確かに上限値よりも大きな値になるが、分布が一様ではなくなってしまい、擬似乱数ではなくなる。
 例えば、サイコロがあったとします。これは一種の擬似乱数生成器として利用できる。2回サイコロを振って、その値を足してしまうと、2〜12の範囲の数値になる。この分布は一様ではなくなる。7が一番出やすく、2や12は一番出にくいからである。また、掛け算を採用すると、1〜36の範囲の数値のうち、11などは絶対に出ない。よって、足し算のときでも掛け算のときでも一様分布になっていないのである。

 例えば、C言語のrand()は0以上32767未満の整数の擬似乱数を返す。このrand()を使って32767以上の擬似乱数値を作りたい場合は、次のようにする。r1,r2はrand()の出力値とする。

擬似乱数r3=r1 × (上限値 + 1) + r2

 つまり、次のようにすればよい。

 int r = rand() * 32768 + rand();

 これで0〜1073741823の擬似乱数を生成することができる。RNAD_MAXが32767(=111 1111 1111 1111SUB{2};=0x7fff)で、15ビット分が有効という前提であれば、次のようにしても上記と同じ結果を返す。結果の値は30ビットになります。

 int val = (rand() << 15) | rand();

 しかし、rand()は精度があまりよくないので、r1とr2に関連があるため、この方式で得たr3は一様分布ではなく偏りが出てしまう。なお、もしr1,r2が完全に独立であれば、r3は一様な擬似乱数になる。