jug7.com
[ home / cgi / juggler / column / diary / bbs / link / welcome ]


乱数メモ




乱数についていろいろ調べたメモ。
誤りや不適切な個所があった場合、メール頂けると嬉しいです。　→　master at jug7.com
1. 乱数とは
2. ソフトウェアによる乱数生成〜疑似乱数
3. perl の rand 関数
4. Z80 の Rレジスタ による疑似乱数生成
5. パチスロにおける乱数生成
6. /dev/random
7. ハードウェアによる乱数生成
8. reference


■ 乱数とは

・　乱数 [ random number ]

出現する値に規則性のない数。

・　物理乱数

確率的な物理現象を使って生成される乱数。
利用される物理現象には、放射性崩壊や、大気の雑音、電気回路の熱雑音などがある。

・　疑似乱数

計算によって求められた乱数。乱数列は、いつかは同じ値が出てきて 繰り返しが起こってしまう。
この繰り返しの周期が十分に長いものであれば、乱数としての精度が高いことになる。


疑似乱数の特徴
1. 短時間でたくさんの乱数を生成することが可能。
2. 同じ初期値を与えた場合には、次の乱数が完全に予測可能。
3. 生成される乱数には一定の周期が生まれる。


ページのトップへ

■ ソフトウェアによる乱数生成〜疑似乱数


プログラムによって疑似乱数を生成できる。

Cライブラリには rand() という関数が備わっている。
乱数生成のアルゴリズムは線形合同法である。

線形合同法



与えた初期値を漸化式へ代入し、次々と乱数を発生させる方法。

漸化式：　Xn = ( A * Xn-1 + C ) Mod M　（ A, C, M は適当な整数。）

Mod M　は、左側の値を右側の値で割ったときの余りを求めるということ。

一般的には M = 2^n , A = ( 8で割って5余る数 ) , C = ( 奇数 ) が使われる。
このように設定すると、0 〜 [M-1] までの数値が周期 M で1回ずつ現れる。


例えば、A = 13 , C = 1, M = 2^3 , 初期値 X0 = 5 とすると、

X1 = 13 * 5 + 1 Mod 8 = 2
X2 = 13 * 2 + 1 Mod 8 = 3
X3 = 13 * 3 + 1 Mod 8 = 0
…

計算していくと、以下のような数列が得られる。

　　2 3 0 1 6 7 4 5 2 3 0 1 6 7 4 5 2 3 …

0〜7 までの数値が周期 8 で繰り返されている。



ある値の Mod 2^n を取るというのは、
下位 n ビットを返すということと同じであり、計算は速い。

例）
　　35 / 8  = 商 4 余 3

    35 を2進数で表すと   100011　下位3ビットは 011 。つまり10進数の 3 である。


C言語の rand 関数では、線形合同法の漸化式の定数に 


　A = 1103515245, C = 12345, M = 2^32



が使われているようだ。


ただし 漸化式によって計算された値の最上位ビットを切り落とすために、
0 〜 2^31 （ およそ 21.4 億 ）までの数値が 周期 2^31で1回ずつ現れる。


rand よりも周期の長い疑似乱数を生成する関数として
drand48 , random などがある。
（ random の周期は 2^62 = およそ461京 ）


また、精度の高い疑似乱数を生成するアルゴリズムとして
Mersenne Twister 法 （ メルセンヌ・ツイスター法 ）がある。 周期は 2^19937 - 1 。

MT法の開発者ページ http://www.math.sci.hiroshima-u.ac.jp/~m-mat/


ページのトップへ

■ perl の rand 関数


rand 数値

により、0 〜 数値 未満 の範囲で浮動小数点数の疑似乱数を返す。

また、srand 関数が呼ばれていない場合は、自動的に srand を実行する。


srand の乱数の種（ seed ）は、/dev/urandom から得た値、もしくは 現在時刻とプロセスID を使用して計算された値を使う。

srand の引数を指定しなかった場合、unix系の perl 5.004 以降では


srand 1000003*time() + 3*$usec + 269*$$ + 73819*${undef} + 26107*\$x

が実行されるようだ。( Perl Monks を参照 )
ただし、このコードは C のコードを perl 風に書いたものであり、このままでは動作せず。

rand 関数自体も、Cライブラリの random() や drand48() を使用しているため、
乱数の質については実装依存となる。



モジュールによって乱数生成に Mersenne Twister 法を使うことができる　→　Math::Random::MT



ページのトップへ

■ X80 のRレジスタによる疑似乱数生成

パチスロには、Z80というCPUが使われているようなので
（ 実際にはZ80互換のCPU。また現在のパチスロ機にも使われているのかは不明 ）

ここで Z80 にも少し触れておくことにする。


Z80 とは、Zilog社の 8ビットマイクロプロセッサのことで、 1980年代半ばまでは CPU としてよく使われていた。

内部には、レジスタという小規模なメモリのようなものがある。

レジスタにも様々な種類があるが、Rレジスタ ( リフレッシュレジスタ ) には、 メモリをリフレッシュするためのアドレスが入っていて、 フェッチされる度に Rレジスタ値はインクリメントされる。
フェッチ → 　マイクロプロセッサが命令を実行する最初の段階において、
　　　　　　　命令コードをメモリから読み出してレジスタに転送すること。
このように適当な時間によってRレジスタの値は変化するため、 疑似乱数生成に使用された。


ちなみにRレジスタは 7ビットレジスタであり 0〜127 までの値が得られる。



ページのトップへ

■ パチスロにおける乱数生成


パチスロ内部での乱数生成方法がわかれば、cgi によるシミュレートが現実に近いものになるだろうと思い調べはじめたんですが。

結局わかったことは、 こんくらい…。



また、実際のパチスロ機種の乱数生成式についてウェブで調べたところ、 ある機種の乱数生成式のみがやたらと目につきました。 やはり乱数生成式とかの詳しい解析情報って公開しちゃいけないことになってるんですかね。
（ 仮に公開したところで誰も読まないからなのか…。 ）



よく目にした、ある機種の乱数生成式ってのが
　乱数値 = ( 前回の乱数値 + Rレジスタ値 *2 + 1 ) & 3FFFh

（ 乱数値は 1秒間に5000回更新 ）
だったんですが。


Rレジスタ値はフェッチされるごとに +1 されるので、
( Rレジスタ値 *2 + 1 )　の部分は 0 〜 255 までの疑似乱数となる。

ちなみに、
16進数の 3FFF → 10進数で 16383 , 2進数では 0011111111111111 .

& はビット演算の論理積。つまり下位14ビットの値を返します ( 0 〜 16383 の範囲の値にする )。 

例）
12345 & 16383

　　12345　→ 2進数で 0011000000111001

　　0011000000111001
 　 0011111111111111
　---------------------
 　 0011000000111001　　  返る値は 12345


16385 & 16383

　　16385　→ 2進数で 0100000000000001

　　0100000000000001
 　 0011111111111111
　---------------------
 　 0000000000000001　　  返る値は 1



先ほどの式では、変化する値として Rレジスタ値 のみなんですが、
これは内部プログラムに依存するだろうから、結局、cgi シミュには生かせず…。

終了。

ページのトップへ

■ /dev/random


OSレベルでの乱数生成。
最近の Linux では /dev/random と /dev/urandom デバイスがあり、良質な 乱数を取得することができる。


/dev/random

エントロピーを持つデータ （ キー入力・マウス操作の時間間隔など ）を 随時集めてプールしておく。プールされたデータに数学的な処理を行い、乱数を生成する。 ただし、十分なデータがプールされていない場合は乱数を生成できない。

/dev/urandom

/dev/random と同様に乱数を生成するが、エントロピー・プール内に 十分なデータが無い場合には、プールされたデータのMD5ハッシュ値から乱数を生成する。


/dev/random をもつ OS は Linux 以外にも多数存在。



[ エントロピー ]
　　乱雑さ。事象の不確かさ。

[ MD5 ]
　　元となるデータから、固定長の疑似乱数的な値を生成する。
　　生成されたハッシュ値から元のデータを復元することは不可能とされている。


ページのトップへ

■ ハードウェアによる乱数生成


放射性崩壊や、電気回路の熱雑音などから物理乱数が得られるが、
現在では安全性の高い、電気回路に生じる熱雑音を源とした乱数生成デバイスが 商品化されている。


乱数を生成するハードウェアについて、ウェブで見つけたものをいくつかリンクしておく。

・　高速物理乱数発生ボード ランダムマスターTM
http://www.t-rs.co.jp/products/p-5/index_j.htm
http://www3.toshiba.co.jp/power/techno/secret/random/index_j.htm

・　物理乱数生成 USB モジュール「Random Streamer」
http://www.fdk.co.jp/whatsnew-j/release041005-j.html
http://randomstreamer.ntl.co.jp/

・　システム工学株式会社
http://www.sic-web.co.jp/technology_rne.html


ページのトップへ

■ reference 参考書籍・サイト

・　プログラミング Perl　第3版 VOLUME 1,2
Larry Wall, Tom Christiansen, Jon Orwant 著、近藤嘉雪 訳、オライリー・ジャパン 出版

・　まつもとまことのホームページ
Mersenne Twister 法の開発者である 松本眞 氏 のサイト。
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/index.html

・　IBM : developerWorks : Security
IBM japan サイト内のセキュリティ面から見た乱数生成に関する記事
http://www-6.ibm.com/jp/developerworks/security/000818/j_playing.html
http://www-6.ibm.com/jp/developerworks/security/000818/j_beating.html
http://www-6.ibm.com/jp/developerworks/security/000908/j_randomsoft.html

・　M.Hiroi's Home Page
Makoto Hiroi 氏のサイト > 続・サルでも書けるＣプログラム講座 > 線形合同法による乱数の生成。
http://www.geocities.jp/m_hiroi/zsaru/zsarub04.html

・　Perl Monks
Perl Monks の srand に関する記事。
http://perlmonks.thepen.com/31600.html

・　Site:Felix
Felix 氏のサイトの Tool box に記載されてあった perl のモジュール Math::Random::MT - The Mersenne Twister PRNG
http://www4.kcn.ne.jp/~felix/Softwares/MathPPM/Math-Random-MT.html

・　SYSTEMAX Software Development
koji 氏のサイト。コンテンツの Z80 の アセンブリャ講座
http://systemax.jp/doc/Z80_text.html

・　うぼらのホームページ
うぼら 氏のサイト > Z-80 マシン語講座。
http://mmm.uec.ac.jp:8081/club/koken/~ubora/

・　Hack the Slot
M 氏が運営されていたページ。謹んでご冥福をお祈り申し上げます。
http://www.zerodivide.com/slot/

・　In My Life... the way of 四郎丸
四郎丸 氏が以前に運営されていたサイト。http://www.archive.org/ より拝見させていただきました。
ページのトップへ




[ home / cgi / juggler / column / diary / bbs / link / welcome ]