Fermat LLCG

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