| -- 目次 -- |
| 参考文献 |
D. Knuth, The Art of Computer Programming Vol 2,
Seminumerical Algorithms, Addison-Wesley
(邦訳, 準数値算法 / 乱数, サイエンス社)
| 1. 疑似乱数 |
計算機は初期条件が同じであれば, 結果は同一ですから, 本当の意味での『でたらめな数』を (ソフト的に) 作ることはできません。 計算機で生成される乱数は, 従って疑似乱数と呼ぶ方が正しく, 色々な生成法があるようです。 しかし実際には大半が線型合同法と呼ばれる方法で生成されています。 線型合同法を最初に考えたのは Lehmer です (メルセンヌ素数の 『Lucas-Lehmer の判定法』 として知られている人です)。
線型合同法 整数 m, a, c, x1 を与えたときに, 次のようにして x2, x3,... を定める。 xn = (a xn-1 + c) mod m (n = 2,3,4,...)このとき {x1,x2, x3,...} をランダムな整数列として選ぶ。
{x1, x2, x3,... } がランダムな整数列とみなせるためには, a, c, m を適当に選ばないといけません。 数列 {x1, x2, x3,... } には周期がありますから, 最も長い周期になるように a, c を選び, しかも同時に統計的に十分でたらめになっていることを 別に検証する必要があります。 また数列 {x1, x2, x3,... } の下の桁が規則的になりやすいため, 下の桁を無視して乱数にすることもあります。
| 2. C 言語の場合 |
ANSI 規格による C 言語では,
rand(); |
によって 0 と RAND_MAX の間のランダムな整数を発生させます。
RAND_MAX は一応使うシステムに依存し,
実際の大きさは stdlib.h の中に書いてあります。
ANSI C の規格で決められていることは RAND_MAX は最低 32767
なければならないことのみです。
従って, ANSI の規格に準拠した C 言語であっても,
計算法などで違っていてもよいと思いますが, rand()
で生成される疑似乱数は線型合同法によるもののみのようです。
rand() では srand() で初期条件
(種 (seed))
を設定することができますが, これは x1 のことです。
実例として Visual C++ の場合を見れば
RAND_MAX = 215 -1 = 32767
|
と設定され, 以下の手順でランダムな整数を出力します。
|
| 3. プログラム |
|
mod 232 |
で整数の加減乗除をすることになります。 また C 言語では整数演算に関して桁をシフトする命令があります。
a = b << r |
とすれば 2 進表示の b を r 桁左へ移動して, a に代入します。 従って 2r 倍することになりますが, あふれた部分は無視します。 また
a = b >> r |
とすれば b を r 桁右へ移動して a に代入します。 従って 2r で割ることになり, この場合もあふれた部分は無視します。
次のプログラムで, Visual C++ の乱数生成方法をチェックできます
a の値をどう変えても差が 0 になるはずです。
#include <stdio.h> #include <stdlib.h> void main(){ int i; unsigned long a = 125,x,y; srand(a); for(i = 0; i< 10; i++){ a = 214013*a + 2531011; a = a<<1; a = a>>1; x = a>>16; y = rand(); printf("%6d, %6d, %6d\n", y, x, y-x); } }
計算機の乱数生成で線型合同法が使用されているのは, 上のプログラムからわかるように, 非常に簡単にしかも高速にできるためです。 しかしこの方法の乱数生成では, 時には非常にまずいことがあるようです。 その時には, 別途ライブラリーを組み込む必要があります。 探せばどこかにあるはずです。