線形合同法のソースを表示

'''線形合同法'''（せんけいごうどうほう、{{lang-en-short|Linear congruential generators, LCGs}}）とは、[[擬似乱数]]列の生成式の一つ。

漸化式
: <math>X_{n+1} = \left( A \times X_n + B \right)\ \bmod\ M</math>
によって与えられる。A、B、Mは[[定数]]で、M[[不等式|>]]A、M>B、A>[[0]]、B≥0である。

==生成==
上の式で、<math>X_0</math>が、乱数の種であり、これに数を代入すると、<math>X_1</math>が得られる。さらに<math>X_2</math>を生成する場合には、<math>X_1</math>を使う。以後、同様に行う。

例えば、定数をそれぞれ、A=3、B=5、M=13、乱数の種<math>X_0</math>=8とすると、（上の式においてはX<sub>n+1</sub>を左辺に置いたが、今回は便宜上、右辺に置く）
: <math>\left( 3 \times 8 + 5 \right)\ \bmod\ 13 = 3</math>
次に乱数を生成する際は前回生成された乱数（今回は3）を使って、
: <math>\left( 3 \times 3 + 5 \right)\ \bmod\ 13 = 1</math>
以下、同じように、
: <math>\left( 3 \times 1 + 5 \right)\ \bmod\ 13 = 8</math>
となる。

===周期性===
生成される乱数列は周期性を持ち、上の例では8→3→1→8→3→……、を繰り返す。この周期は最大でMであり、以下の条件が満たされたときに最大周期Mをもつ。
#BとMが互いに素である。
#A-1が、Mの持つ全ての素因数で割りきれる。
#Mが4の倍数である場合は、A-1も4の倍数である。

A=13、B=5、M=24の組み合わせなどがそれに当たる。

B=0のときは、0→0→0...というループがあるため、周期がMとなるAとMの組合せはない。M-1が、B=0の場合の最大の周期であり、これも最大周期と考えることもある。

==長所==
*状態を記憶するのに必要なメモリの他には、作業用のワーキングメモリをほとんど必要としない。実用的な擬似乱数アルゴリズムでは最少の部類に属する。
*低機能な[[プロセッサ]]にも効率よく実装できる。素朴には[[乗算]]と[[除算]]が必要そうに見えるが、(1)定数による乗算なのでシフトと加減算の組合せにできる (2)除算そのものが必要なのではなく剰余が得られれば良いので[[合同式|合同算術]]による式変形が可能であり、乗算も含めて変形することでより効率化できる (3)剰余算についても、よく使われる 2<sup>n</sup>-1 の形をした値による剰余は特別な場合として効率化ができる、といった特徴のためである。
*そのため、専用回路化すら容易である（ただし、適切な[[M系列]]を[[線形帰還シフトレジスタ|LFSR]]で実装したほうが、回路で計算するにはより効率が良い上に、乱数としての質も良い）。
*問題点は多いが、どのような問題があるか、どうやって回避すればいいかが十分に研究されている（ただし、回避しなければならない使い方を回避していなかった事例を挙げて、悪い結果を生成系のせいにされていることがしばしば見られる）。

==短所==
[[暗号論的擬似乱数生成器]]ではなく、そのまま[[暗号]]に使用してはならない。

線形合同法一般の欠点に、多次元で規則的に分布するという性質がある。線形合同法による乱数列r<sub>0</sub>, r<sub>1</sub>, r<sub>2</sub>, r<sub>3</sub>, ... から(r<sub>0</sub>, r<sub>1</sub>), (r<sub>1</sub>, r<sub>2</sub>), (r<sub>2</sub>, r<sub>3</sub>), ... のように順番に割り当ててプロットすると、それが疎になるのはしょうがないのだが（例として、全部で10000個しかない点を、10000x10000 の矩形にプロットすることになるのだから、稠密にはなりえない）、一定の間隔の平面上に点が並んでしまうのが問題である。印象的にこれを表現したフレーズに ''Random numbers fall mainly in the planes.'' （乱数は、主に平面（プレイン）に落ちる）というものがあり、「スペインの雨は主に平野（プレイン）に降る」（The rain in Spain stays mainly in the plain.）のパロディである<ref>引用元については [[スペインの雨]] を参照。</ref><ref>[http://www.jstor.org/stable/58853 Random Numbers Fall Mainly in the Planes]</ref><ref>このタイトルで書かれた文献の著者は George Marsaglia（[[:en:George Marsaglia]]）だが、[[ドナルド・クヌース]]はこの表現の出典を（[[The Art of Computer Programming|TAoCP]]にて）[[ウォレス・ギヴンス]]としている。</ref>。科学技術シミュレーションで3次元の点の位置などを生成する場合に問題となる。

下位ビットのランダム性が低い。Mの値によっては、最下位に近いビットはほとんどランダムでなく、完全に規則性を持っていることすらある。たとえばMが偶数の場合（コンピュータでの実装が楽であるために、Mに2の冪を採用した場合はこれに当たる）、最下位ビットは、同じものが出続けるか、0と1が交互にでるかのどちらかである。すなわち、偶数ばかりが出る、奇数ばかりが出る、偶数と奇数が交互に出る、のどれかになるということである（最大周期ならば偶数と奇数が交互に出る）。

大量に乱数列を消費する科学技術シミュレーションなどでは、周期の短さ（たとえば32ビットでは最大周期でも約40億）が問題になる。

[[プログラミング言語]]処理系に附属するライブラリの乱数列生成器（たとえば[[rand|rand(3)]]や<code>java.util.Random</code>など）が、線形合同法を利用している場合があるため、たとえばサイコロの目を生成する場合は<code>rand() % 6 + 1</code>としてはならない。前述のように周期2で偶数と奇数が循環するような場合、その規則性がそのまま顕れてしまう。<code>rand() / (RAND_MAX / 6 + 1) + 1</code>のようにすればランダムになる（注。このコードは考え方を示すものであり、厳密に1/6の確率になるものではない）。<!--これは、処理系依存であるRAND_MAXが一般的に6で割り切れない数値のため、%演算では1から6の数字が均等に発生しない事が原因である。RAND_MAXが大きいほど、<code>rand() % 6 + 1</code>のコードは均等な発生確率に収束する。
しかしながら強力なランダム性が必要であれば、そもそも線形合同法ではなく別のアルゴリズムを利用するべきである。--><!-- ←下位桁は均等ではある（規則的なのでむしろ均等過ぎるほど）。これを書いた人物は「ランダム性」＝「均等」と誤解しているようだ -->

==例==
==={{Anchors|ParkMiller}}Park & Miller===
Stephen K. Park と Keith W. Miller が、彼らのサーベイ中で「最低基準」として示したもので、より良い選択肢が無いのならば、自作などせずにこれを使うべしというもの。
: <math>X_{n+1} = \left( 48,271 \times X_n \right)\ \bmod\ (2^{31} - 1)</math>
C言語による実装例が「comp.lang.c FAQ list · Question 13.15」の回答中にある<ref>[http://c-faq.com/lib/rand.html comp.lang.c FAQ list · Question 13.15] ただしソースコードでは乗数が 16807 になっているので注意すること。48271 を使ったほうが（もしかしたら計算がわずかに重くなるかもしれないが）少し良い乱数列になる。ソースコード中のその数の部分を書き換えるだけでよい。</ref>。

===由来不詳===
由来不詳だが、よく実装が見られるもの。
: <math>X_{n+1} = \left( 1,103,515,245 \times X_n + 12,345 \right)\ \bmod\ 2^{32}</math>
C言語による実装例が、POSIXのrandの解説中（informative扱いのEXAMPLESとして、であるが）にあるため<ref>http://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html#tag_16_473_06_02</ref>か、2017年現在のウェブコンテンツなどにも時折見られるが（例えばRosetta Codeの線形合同法のサンプルに「BSD formula」という名前で示されている）前節のPark & Millerよりも質が悪い。特に（POSIXにあるコードでは下位桁を捨てて回避しているが）、最下位ビットは周期2、次のビットは周期4、次のビットは周期8、……のように、下位桁に完全な規則性がある。また、由来は不詳だが少なくともBSDよりは古く、Unixバージョン7の /usr/src/libc/gen/rand.c に見られる。

==注・出典==
<references/>

==参考文献==
#Park and Miller, "Random Number Generators: Good Ones are Hard to Find"
#結城浩著『暗号技術入門 - 秘密の国のアリス』、ソフトバンク、ISBN 4-7973-2297-7、pp.305-307.

==関連項目==
* [[Permuted congruential generator]] - 線形合同法の出力を加工して統計的性質を改善したアルゴリズム。

[[category:乱数|せんけいこうとうほう]]
[[category:数学に関する記事|せんけいこうとうほう]]