Fermat LLCG (Lehmer LCG (Linear Congruential Generator)) という擬似乱数列生成系の提案です。
ParkとMillerのminimal standardにすら遠く及ばない簡易な生成系ですが、用途によってはこれで十分なこともあるでしょう。
(おそらく最大の)フェルマー素数である65537を法とすることが特徴の、素数を法とする乗法合同法による擬似乱数列生成系です。線形合同法および乗法合同法や検定の詳細については文献(The Art of Computer Programming 2巻、等)を参照してください。
生成式 `X_(n+1) = aX_n mod 65537` の `a` としては、次の4つの数を候補とします。
15978, 19290, 22348, 23272
この4数はスペクトル検定で、2〜6次元の「全ての次元でそれほど悪くない」結果になるものです。それぞれのひとつの次元ではこれより良い結果になる数もありますが、別の次元で極端に悪いため候補から外しました。The Art of Computer Programming の §3.3.4 表1 のフォーマットに倣って `nu_t^2` を示すと次のようになります。
`a` | `nu_2^2` | `nu_3^2` | `nu_4^2` | `nu_5^2` | `nu_6^2` |
---|---|---|---|---|---|
15978 | 58613 | 1350 | 214 | 85 | 35 |
19290 | 60314 | 1382 | 226 | 58 | 44 |
22348 | 67985 | 1510 | 217 | 49 | 35 |
23272 | 66266 | 1366 | 247 | 40 | 40 |
生成式そのままでは [1, 65536] の範囲にある整数を生成しますが、2進法との相性が悪いですから 65536 を 0 で表すことにして [0, 65535] とします。機械語命令では「ゼロの時ジャンプ」という1命令が追加で必要になりますが、そう大きなコストでもないでしょう。
ここでは8086での実装例を示します。このアセンブリ言語の記法は私が実験に使ったLSI C-86付属のアセンブラr86のもので一般的ではありませんが、同処理系を実装されたkmoriさんを偲んでそのまま掲載します。
CGROUP GROUP TEXT DGROUP GROUP DATA,BSS TEXT CSEG DATA DSEG BSS DSEG TEXT CSEG fllcg_srand_:: MOV [fllcg_state_].W,AX RET A EQU 15978 fllcg_rand_:: PUSH DX MOV AX,[fllcg_state_].W MOV BX,A MUL BX SUB AX,DX JZ _1 ADC AX,0 MOV [fllcg_state_].W,AX POP DX RET _1: MOV AX,1-A MOV [fllcg_state_].W,AX POP DX RET BSS DSEG EVEN fllcg_state_: RS 2 END