RSS | ATOM | SEARCH
スポンサーサイト

一定期間更新がないため広告を表示しています

author:スポンサードリンク, category:-,
-, -, - -
擬似乱数
 擬似乱数についての話です。

1.擬似乱数の概要
通常のコンピュータでは、決まった値は出せますが、サイコロみたいに気まぐれな値は出せません。
このため、サイコロを振ったふりをする事になります。
本当の乱数と区別して擬似乱数と呼ばれます。

大雑把には、以下のような仕組みです。
・大量の値を予め持っておき、順番に1個ずつ出す。
・すべての値を出したら、次は最初の値を出して、以下繰り返す。

ただし、予め保持する値が一様で、次の値を予測するのが難しくて、繰り返す頃には忘れている程の量である、という条件が付きます。
この条件を満たせばサイコロを演じる事ができます。満たさなければインチキだと思われるかもしれません。

実際は、大量の値を保持するのは色々都合が悪いので、自動生成する仕組みを使います。


2.具体的なアルゴリズム

具体的な仕組みをアルゴリズムと言いますが、現状使われている擬似乱数のアルゴリズムを紹介します。

2−1.線形合同法
定数AとBとCを用いて、以下の式で定義されます。
[次の値] = ([直前の値] × A + B) % C

理論上は、加算と乗算と剰余を使いますが、通常は、速度の都合で、剰余は論理積で代用されます。

掛け算を使用するため、やや遅くなります。
※現在のコンピュータでは、一般的には、論理演算、加減算、剰余算、の順に遅くなります。
また、そのまま使うと偶数と奇数が交互に出るなど、不規則性に問題があります。

2−2.M系列
Nビットの数列に対して、定数Aを用いて、以下のようなビット単位の操作で定義されます。
[次の値の (k + 1)ビット目] = [直前の値の (k)ビット目]
[次の値の 最初のビット] = [直前の値の 最後のビット] xor [直前の値の Aビット目]
※M系列とは、この操作で全部ゼロ以外のすべてのビット列を生成できる、都合の良いパラメータを指定したものです。
※基本的には1ビットずらしますが、1ビット以上変化を与える事で、ぐるっと回っただけでは簡単には元に戻らないようになります。
※一般的なM系列ではこのように1ビットだけで済むわけではありませんが、ここでは都合の悪いものは無視します。

演算は、排他的論理和(xor)とシフトだけを使うので、コンピュータ上では速いです。
そのまま使うと、直前の値と比べて、ひとつずらして1ビット変えるかどうかだけなので、不規則性に問題があるかもしれません。

3.実測

3−1.環境
ハード:クロック2.8[ギガ毎秒]
ソフト:java1.6
測定値:1億回の実行時間。

3−2.測定結果

・128ビットのM系列(Xorshift)
1050[ミリ秒]

・800ビットのM系列(TT800)
1536[ミリ秒]

・48ビットの線形合同法(java.util.Random)
3027[ミリ秒]

3−3.感想と考察
クロックに換算すると、1秒が28クロックです。
メルセンヌツイスタ(19937ビットのM系列みたいなもの)も試したかったのですが、手元にプログラムがありません。。
現状の乱数といえばメルセンヌツイスタばかりの現状はどうなのかなと疑問に思うので、
本当は、実行速度の比較をして他のアルゴリズムも良いよね、という話をしたかったです。

やっぱり、M系列の方が線形合同法より速いです(今回は2〜3倍程度ですが、精度を揃えるともっと差が開くはず)。
ただし、通常のプログラムでは圧倒的に他の処理時間が長いため、この差は無視できます。

精度と速度を考えると、現状では128ビットのM系列が良いのかなと思います。

author:たかき, category:-, 15:46
comments(1), trackbacks(0), - -
スポンサーサイト
author:スポンサードリンク, category:-, 15:46
-, -, - -
Comment
私には未知の世界・・・すごすぎます。
ころだ, 2010/06/22 5:41 PM









Trackback
url: http://maildegift.jugem.jp/trackback/25