疑似乱数
ナビゲーションに移動
検索に移動
疑似乱数は、アルゴリズムによって生成された乱数のことである。このサイト(Enpedia)でよくある言い方を借りれば、「謎の乱数もどき」である。[1]
概要[編集]
完全な乱数を得ようとするならば、量子力学に頼るしかなく、かなり面倒くさい。
とはいえ、実用上「乱数」が必要なこともあるわけで、疑似乱数を生成することが要求されるのだが、いまのところ「質の高い乱数を生成するアルゴリズム」というのは数少ない。
広く知られているものとしては線形合同法があるが、あまり質がよくない。現在知られている質の良い乱数生成法としては「最長周期律法（M系列法）」や「メルセンヌ・ツイスター」程度である。
これらのコードに「人間が乱数っぽく感じる[2]ようにする工夫[3]」をほどこして使っているのが現状である。
疑似乱数の生成方法[編集]
ある数(これを乱数の種という)を前述のアルゴリズムに入力すると、アルゴリズムの中で複雑な計算が行われ、疑似乱数が生成される。その疑似乱数を種として生成を繰り返すことで、たくさんの乱数を生成できる。
この「乱数の種」が重要なポイントで、毎回同じ数が種だと同じ乱数が返ってくる。一般的には現在時刻を利用する。
平方最中法[編集]
- nけたのシードを用意し、二乗する。
- 二乗した答えが2*nけたになるよう、0を補う。
- 真ん中のn桁の数が乱数。
1111*1111=01234321 →2343 2343*2343=05489649 →4896 4896*6896=23970813 →9708 …
線形合同法[編集]
最も簡単な方法、それが線形合同法。
- N(シード)、A、B、Cの数を用意する。
- (A*N+B) mod C(AとNをかけてBを足してCで割った余り)が乱数。
(A=1、B=2、C=3、N=4) (1*4+2) mod 3=0 (1*0+2) mod 3=2 (1*2+2) mod 3=1 (1*1+2) mod 3=0 … (0、2、1を無限ループ)
線形帰還シフトレジスタ[編集]
ハードウェア上でも実装可能で、現役で使われている。
図は[1]より
1.8,6,5,4ビット(8ビットの際の最適解。ビット数に応じて変わる)を取り出しXORで結合する
2.右に1ビットシフトする（ビット全体をずらし、8ビット目は消滅する）
3.XORで結合したビットを、先頭に入れる
| --------> Shift --------> |
+---+---+---+---+---+---+---+---+ - +
| * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 :
+-^-+---+---+---+---+---+---+---+ - +
| | | | |
| | | +--XOR--+
| | | |
| | +--XOR--+
| | |
| +--XOR--+
| |
+-------------------+
シフトレジスタ全体を一つの乱数として見ることもできるし、一つだけ取り出して使うこともできる。
全てのビットが0になることはない。(初期値としてオール0を指定すると、永遠に0を出力する。)
コード[編集]
Java による、原始多項式を用いた最長周期法によるコードである。
/**
* Luwis & payne
* M 系列法（最長周期法）による
* 疑似乱数の生成
* x^pwp^ + x^pwq = 1
*/
public class RandLP {
public static void main( String[] args ) {
_main();
return;
}
private static void _main() {
System.out.println(Integer.MAX_VALUE);
for (int ncnt = 0; ncnt < 100; ncnt+=1) {
//LP(52);
System.out.println(LP2(52));
}
/*
for (int i = 0; i < 89; i+=1) {
// System.out.print(LP(32768)+ ", ");
System.out.print((int)(LP(1) * Integer.MAX_VALUE) + ", ");
if ((i % 5) == 0) System.out.println();
}
*/
return;
}
static final int IP = 89;
static final int PWQ = 38;
static final int IQ = IP - PWQ;
static final int MAX = Integer.MAX_VALUE;
static int j = 0;
static int m[] = {
1592226944, 1984348928, 1592225792, 2015294208, 424637056,
2077481472, 387402720, 2083704192, 624210816, 1722843392, //10
1354712320, 1797627008, 444747744, 163130688, 1824820992,
681686400, 907007552, 747478976, 1919608448, 2083701376, //20
1824821504, 1592227968, 747476416, 1984354560, 1493592832,
2083706368, 1919609856, 999998272, 1132738560, 681684288, //30
1919607936, 1984353280, 132187704, 1147480320, 907002176,
1654435200, 2083706752, 1592221696, 163132096, 2015290624, //40
1919608832, 387402912, 63775904, 945283712, 1919610368,
841217024, 945289024, 1824818816, 1465799808, 1632732160, //50
227869760, 681688960, 1202196736, 907006336, 1906826624,
2147478400, 1240478336, 1654438784, 63774792, 624207360, //60
1400010240, 1309745920, 1919612288, 837735296, 1418951424,
747473472, 1702736384, 1240478720, 444746848, 1078530432, //60
1972103168, 70008336, 322661760, 2077480320, 1972105216,
2015291904, 1760083584, 1702738816, 907004032, 653889920, //70
1919610624, 1465797632, 1309751680, 1078532864, 1654435712,
1523274624, 1760078464, 493044128, 1523277184, 1400006400, //80
1972103168, 1202194688, 322661760, 2077480320, 1972105216,
555259072, 1592223488, 1984352384, 1919613696
};
public static float LP(int range) {
int ipx, iqx;
j = ( j + 1 ) % IP;
int k = ( j + IQ) % IP;
m[ j ] ^= m[ k ];
// return ((float)( m[j] * (double)range) / (float )MAX));
return ((float) m[j]) / ((float)MAX);
}
public static long LP2(int range) {
int ipx, iqx;
j = ( j + 1 ) % IP;
int k = ( j + IQ) % IP;
m[ j ] ^= m[ k ];
// return ((float)( m[j] * (double)range) / (float )MAX));
return ((long) m[j]) * (long)range / ((long)MAX);
}
}
このサイト上での乱数の生成方法[編集]
このサイトでも、テンプレート:おすすめピックアップやおみくじで簡易な疑似乱数が使われている。どんな方法で生成されているのかについては各ページのコードを参照。
参考文献[編集]
- 伏見正則「一様乱数の発生法について」（数学セミナー vol.7 No.10、（1979年10月号）、日本評論社）