職場で作っている検証用システムでこういうことをやりたかった。
出力値の候補を16個用意しておいて、これを一定時間ごとに切り替える。
この16個の値をいろいろな順番で出力したい。
16個の順番を並べる全パターンは16!=2.1×1013個もあるから、
全切替パターンをプログラムに記載するのは不可能である。
ということで乱数を使いたかったのだが、乱数ライブラリなんてないんだよな。
自分で疑似乱数生成器を作ろうということで、まず思いついたのはメルセンヌツイスター。
しかしどんな実装なのだろうと調べたが、概要を見て無理だと思った。
というのも624個もの32bit整数を内部状態として持つ必要があるからである。
周期が長くランダム性が高い疑似乱数が生成できる方法だが、
そのためには内部状態としてそこそこ巨大なものを持たないといけない。
だからといって線形合同法はわりと規則性が見えてしまうよなぁ。
デジタル回路でよく使われるLFSRはビットシフトが主体なので、これもほとんど規則性のある変化しかしない。
もうちょっと実装が容易で質の良い方法がないかと思ったら、Lagged Fibonacci法というのを見つけた。
疑似乱数列 Sn を Sn=Sn-j + Sn-k(mod m)という形で計算するというもの。
過去の乱数を2つ取り出して足すという簡単な計算ですね。
足し算以外の演算子、例えばXORでもLagged Fibonacciではあるようだが、普通は別の名前が付いている。
ただ、いろいろ調べてわかったのは、この成否を決めるのはk,jの数字で、
この最大値がある程度大きくて、初期値としてそこそこ質の良い乱数が用意できるかどうかが決め手になるようだ。
最初、k=1,j=7で試していたのだが、下位ビットの質がよくない。
それで典型例として書いてあったk=31,j=63でやると下位ビットまで質がよさそう。
質の良い乱数を作るには内部状態を大きくしなければならないと。単純にはそういう話らしい。
メルセンヌツイスターほどではないし、バッファさえ持てればよいので実現性はあるが。
しかし線形合同法だって下位ビットを捨てればそこそこ質がよいという話もあるんだよな。
線形合同法の欠点として、2個の乱数をペアにすると偏るというのがあって、
それを今回の目的に適用すると、出力値の遷移が偏ってしまうということになる。
ただ、下位ビットを捨てればその影響は減るという話があって、それは繰り上がりがあるからなんだと思うけど。
線形合同法 Xn=A×Xn-1 + B (mod m) で、A=214013,B=2531011,m=232(Visual Studioで使われている数字らしい)を適用して、
この結果を4bitごとに区切って2つペアにすると、下位12ビットまでの組み合わせは発生回数0回というのが存在する。
しかし、15～12bitでは発生回数が最大・最小の回数差がほとんどなくなる。
実際、Visual Studioでは下位16ビットを捨てているらしい。
32bitで計算して下位16bitを捨てても、16bit残って、これは16個の出力値選択を同時に4つ操作出来るということである。
それで実用上十分なランダム性が得られるように見えるので、これでよいのでは?
ただ、この下位ビットをいくつ捨てるとうまくいくのかというのもようわからん話ですがね。
疑似乱数の評価も理論的なところとそうでもないところがあるからなんとも。
というわけで最初は線形合同法を忌避してLagged Fibonacci法を選ぼうとしたが、
それはそれで乱数を63個置いておかないといけないのでけっこう大変だと。
線形合同法はなんやかんやシンプルなのが魅力である。
それで下位ビットを捨てればある程度いけるやろというのも知見であろう。
シミュレーションで露骨に偏らないことが確認出来たら、それでもいいのかもね。
今回の用途で求められるのはその程度のランダム性だし。
というわけでランダムに切り替わるというのもそれはそれで難しいという話ですね。
このシステムで他に乱数的に使えるものがないか考えてみたけど、
どうにも難しそうと言うことで、乱数を自分で用意しなければならなくなったと。
ところがこの疑似乱数というのは本当に難しい。
真の乱数発生器を取り付けたいぐらいめんどくさいが、真の乱数もそれはそれで難しいらしい。