整数演算の乱数
2000-10-06 作成 福島
2000-10-17 更新 福島
アーキテクチャやハードウェアの異なるコンピュータ間で同じ乱数を発生させたいと思ったことはないでしょうか？
多くの乱数発生ライブラリは 0 <= x < 1 という乱数を発生させるため、浮動小数点演算を行います。
また、コンピュータのアーキテクチャによって、「有効桁数」や「丸め誤差」が存在します。
そもそも演算のビット数やアルゴリズムが違っていたりもします。
これらの要因により、乱数列に違いが生まれてしまいます。
モンテカルロ法やニュートン法等での乱数の使用であればこれでも問題はないのですが、
簡単な暗号に利用したりバグを再現する場合等はこれが邪魔になります。
演算に整数のみを使用し、そのビット幅を制限すればこの問題は回避できます。
ここでは、乱数の SEED さえ同一であれば同じ擬似乱数列を算出したいと思います。
線形合同法という乱数の発生方法を使用します。
線形合同法というと難しそうですが、要するに
掛け算をした答えの一部分が乱数の様に見える
というのを利用したものです。
例：
3 * 69069 + 1 = 207208 : 0000 0000 0000 0011 0010 1001 0110 1000(b)
3
207208 * 69069 + 1 = 1426747465 : 0101 0101 0000 1010 0111 0000 0100 1001(b)
21770
1426747465 * 69069 + 1 = 291020662 : 0001 0001 0101 1000 1001 1111 0111 0110(b)
4440
291020662 * 69069 + 1 = 59158399 : 0000 0011 1000 0110 1010 1111 0111 1111(b)
902
59158399 * 69069 + 1 = 1497562036 : 0101 1001 0100 0010 1111 1011 1011 0100(b)
22850
1497562036 * 69069 + 1 = 3709842213 : 1101 1101 0001 1111 1011 0011 0010 0101(b)
56607
アンダーラインの部分が乱数の様に見える
これは、オーバーフローを無視した演算を利用しているので、上位ビットであるほど乱雑度が増します。
上に挙げた乗数には 69069 という数値を使っていますが、このほかにも
1664525
39894229
48828125
1566083941
1812433253
2100005341
という数値がよく知られています。
プログラム
本当は全てを Perl または C で作成したいのですが、
・インターネットでは Perl が主流
・Perl では unsigned long の演算ができない
という理由により、Perl の中から C を呼び出す形で実現します。
C のプログラムはここ、Perl のプログラムはここです。
重要なのは C の演算部分と、Perl からの呼び出し部分です。
※注意点
この C のプログラムでは、32 ビット限定の演算を行っています。
(& 0xFFFFFFFF のところ)
これは、いまどきのコンピュータで走る C は殆ど unsigned long が 32 ビット以上であるということと、
32 ビットを超えるシステムとそうでないシステムでもきちんと同期するようにしたための配慮です。
この Perl のプログラムでは、演算結果と乗数を両方 C で作成した実行ファイルに渡してしていますが、
これは、ファイル書出し（読込み）を避けるようにしたための配慮です。
(複数のプロセスで起動したとき、ファイルの衝突を考える必要が無い)
それでは、乱数を発生させてみましょう