線形合同法とは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > 線形合同法の意味・解説 

線形合同法

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/04/10 11:10 UTC 版)

ナビゲーションに移動 検索に移動

線形合同法(せんけいごうどうほう、: Linear congruential generators, LCGs)とは、擬似乱数列の生成式の一つ。

漸化式

によって与えられる。A、B、Mは定数で、M>A、M>B、A>0、B≥0である。

生成

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

例えば、定数をそれぞれ、A=3、B=5、M=13、乱数の種=8とすると、(上の式においてはXn+1を左辺に置いたが、今回は便宜上、右辺に置く)

次に乱数を生成する際は前回生成された乱数(今回は3)を使って、

以下、同じように、

となる。

周期性

生成される乱数列は周期性を持ち、上の例では8→3→1→8→3→……、を繰り返す。この周期は最大でMであり、以下の条件が満たされたときに最大周期Mをもつ。

  1. BとMが互いに素である。
  2. A-1が、Mの持つ全ての素因数で割りきれる。
  3. 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)除算そのものが必要なのではなく剰余が得られれば良いので合同算術による式変形が可能、等の理由から効率的な式に変形できる。
  • そのため、専用回路化すら容易である(ただし、適切なM系列LFSRで実装したほうがより効率良く乱数としての質も良い)。
  • 問題点は多いが、どのような問題があるか、どうやって回避すればいいかが十分に研究されている。

短所

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

線形合同法一般の欠点に、多次元で規則的に分布するという性質がある。線形合同法による乱数列r0, r1, r2, r3, ... から(r0, r1), (r1, r2), (r2, r3), ... のように順番に割り当ててプロットすると、それが疎になるのはしょうがないのだが(例として、全部で10000個しかない点を、10000x10000 の矩形にプロットすることになるのだから、稠密にはなりえない)、一定の間隔の平面上に点が並んでしまうのが問題である。印象的にこれを表現したフレーズに Random numbers fall mainly in the planes. (乱数は、主に平面(プレイン)に落ちる)というものがあり、「スペインの雨は主に平野(プレイン)に降る」(The rain in Spain stays mainly in the plain.)のパロディである[1][2][3]。科学技術シミュレーションで3次元の点の位置などを生成する場合に問題となる。

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

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

プログラミング言語処理系に附属するライブラリの乱数列生成器(たとえばrand(3)java.util.Randomなど)が、線形合同法を利用している場合があるため、たとえばサイコロの目を生成する場合はrand() % 6 + 1としてはならない。前述のように周期2で偶数と奇数が循環するような場合、その規則性がそのまま顕れてしまう。rand() / (RAND_MAX / 6 + 1) + 1のようにすればランダムになる(注。このコードは考え方を示すものであり、厳密に1/6の確率になるものではない)。

Park & Miller

Stephen K. Park と Keith W. Miller が、彼らのサーベイ中で「最低基準」として示したもので、より良い選択肢が無いのならば、自作などせずにこれを使うべしというもの。

C言語による実装例が「comp.lang.c FAQ list · Question 13.15」の回答中にある[4]

由来不詳

由来不詳だが、よく実装が見られるもの。

C言語による実装例が、POSIXのrandの解説中(informative扱いのEXAMPLESとして、であるが)にあるため[5]か、2017年現在のウェブコンテンツなどにも時折見られるが(例えばRosetta Codeの線形合同法のサンプルに「BSD formula」という名前で示されている)前節のPark & Millerよりも質が悪い。特に(POSIXにあるコードでは下位桁を捨てて回避しているが)、最下位ビットは周期2、次のビットは周期4、次のビットは周期8、……のように、下位桁に完全な規則性がある。また、由来は不詳だが少なくともBSDよりは古く、Unixバージョン7の /usr/src/libc/gen/rand.c に見られる。

注・出典

  1. ^ 引用元については en:The Rain in Spain を参照。
  2. ^ Random Numbers Fall Mainly in the Planes
  3. ^ このタイトルで書かれた文献の著者は George Marsaglia(en:George Marsaglia)だが、ドナルド・クヌースはこの表現の出典を(TAoCPにて)ウォレス・ギヴンスとしている。
  4. ^ comp.lang.c FAQ list · Question 13.15 ただしソースコードでは乗数が 16807 になっているので注意すること。48271 を使ったほうが(もしかしたら計算がわずかに重くなるかもしれないが)少し良い乱数列になる。ソースコード中のその数の部分を書き換えるだけでよい。
  5. ^ http://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html#tag_16_473_06_02

参考文献

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

関連項目


線形合同法 (linear congruential method)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/09 18:40 UTC 版)

擬似乱数」の記事における「線形合同法 (linear congruential method)」の解説

詳細は「線形合同法」を参照 線形合同法の X n + 1 = ( A × X n + B ) mod M {\displaystyle X_{n+1}=\left(A\times X_{n}+B\right){\bmod {M}}} において、B=0場合区別して特に乗算合同法、B>0 の場合区別して特に混合合同法と言うことがある。

※この「線形合同法 (linear congruential method)」の解説は、「擬似乱数」の解説の一部です。
「線形合同法 (linear congruential method)」を含む「擬似乱数」の記事については、「擬似乱数」の概要を参照ください。

ウィキペディア小見出し辞書の「線形合同法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「線形合同法」の関連用語

線形合同法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



線形合同法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの線形合同法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの擬似乱数 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS