نمایش مبدأ برای مولد همگرایانه خطی

[[پرونده:Linear_congruential_generator_visualisation.svg|بندانگشتی|480x480پیکسل| دو LCG مدولو-۹ نشان می‌دهد که چگونه پارامترهای مختلف منجر به طول چرخه‌های مختلف می‌شود. هر ردیف وضعیت را نشان می‌دهد که در حال تکامل است تا زمانی که تکرار شود. ردیف بالا یک ژنراتور با ''m'' را نشان می‌دهد = ۹، ''الف'' = ۲، ''ج'' = ۰ و دانه ۱ که چرخه ای به طول ۶ ایجاد می‌کند. ردیف دوم همان ژنراتور با دانه ۳ است که یک چرخه به طول ۲ تولید می‌کند. با استفاده از ''a'' = ۴ و ''ج'' = ۱ (ردیف پایین) طول چرخه ۹ را با هر دانه در [۰، ۸].]]
یک '''مولد همگام خطی''' ('''L C G''') [[الگوریتم|الگوریتمی است]] که دنباله ای از اعداد شبه تصادفی محاسبه شده با یک [[تابع تکه‌ای خطی|معادله خطی تکه ای]] ناپیوسته را به دست می‌دهد. این روش یکی از قدیمی‌ترین و شناخته شده‌ترین الگوریتم‌های [[مولد اعداد شبه تصادفی]] را نشان می‌دهد. تئوری پشت آن‌ها نسبتاً آسان است و به راحتی و سریع پیاده‌سازی می‌شوند، مخصوصاً روی [[سخت‌افزار رایانه]] که می‌تواند [[هم‌نهشتی (نظریه اعداد)|محاسبات مدولار]] را با برش بیت ذخیره‌سازی ارائه دهد.

مولد با [[رابطه بازگشتی|رابطه عود]] تعریف می‌شود:

: <math>X_{n+1} = \left( a X_n + c \right)\bmod m</math>

جایی که <math>X</math> [[دنباله|دنباله ای]] از مقادیر شبه تصادفی است و

: <math> m,\, 0<m </math> - " [[عملیات پیمانه|مدول]] "
: <math> a,\,0 < a < m</math> - "ضریب"
: <math> c,\,0 \le c < m</math> - "افزایش"
: <math> X_0,\,0 \le X_0 < m</math> - "seed" یا "start value"

ثابت‌های [[عدد صحیح|صحیحی]] هستند که مولد را مشخص می‌کنند. اگر ''c'' = ۰، مولد اغلب یک '''مولد همگام ضربی''' نامیده می‌شود. اگرc ≠ ۰، این روش را یک '''مولد متجانس مختلط''' می‌نامند. {{R|KnuthV2|p=۴-}}

زمانی که ''c'' ≠ ۰، یک [[ریاضی‌دان|ریاضیدان]] عود را [[تبدیل آفین|تبدیلی وابسته]] می‌نامد، نه یک تبدیل [[نگاشت خطی|خطی]]، اما این نام اشتباه در [[علوم رایانه|علم کامپیوتر]] به خوبی تثبیت شده‌است. {{Rp|1}}

== تاریخ ==
ژنراتور لمر در سال ۱۹۵۱ منتشر شد<ref>{{Cite journal|last=Lehmer|first=Derrick H.|date=1951|title=Mathematical methods in large-scale computing units|journal=Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery|pages=141–146}}</ref> و ژنراتور همخوانی خطی در سال ۱۹۵۸ توسط دبلیو ای تامسون و ای. روتنبرگ منتشر شد.<ref>{{Cite journal|last=Thomson|first=W. E.|date=1958|title=A Modified Congruence Method of Generating Pseudo-random Numbers|journal=The Computer Journal|volume=1|issue=2|pages=83|doi=10.1093/comjnl/1.2.83|doi-access=free}}</ref><ref>{{Cite journal|last=Rotenberg|first=A.|date=1960|title=A New Pseudo-Random Number Generator|journal=Journal of the ACM|volume=7|issue=1|pages=75–77|doi=10.1145/321008.321019}}</ref>

== طول دوره ==
یکی از مزایای ال سی جی‌ها این است که انتخاب مناسب پارامترها منجر به یک دوره شناخته شده و طولانی می‌شود. اگر چه نه تنها معیار، بیش از حد کوتاه یک دوره یک نقص کشنده در یک مولد عدد شبه تصادفی است.

در حالی که ال سی جی‌ها قادر به تولید هستند اعداد شبه تصادفی که می‌تواند رسمی باشد تست‌های تصادفی، کیفیت خروجی به انتخاب پارامترها بسیار حساس است ''m'' و ''a''.{{R|Marsaglia68|KnuthV2|Park88|Hörmann92|LEcuyer99|Steele20}} به عنوان مثال، ''a'' = ۱ و ''c'' = ۱ یک مدول ساده تولید می‌کند-''m'' شمارنده، که دارای یک دوره طولانی، اما واضح است که غیر تصادفی است.

از لحاظ تاریخی انتخاب‌های ضعیف برای ''a'' به پیاده‌سازی بی اثر از ال سی جی منجر شده‌است. یک مثال به خصوص گویا از این است راندو که به‌طور گسترده‌ای در اوایل دهه ۱۹۷۰ مورد استفاده قرار گرفت و منجر به نتایج بسیاری شد که در حال حاضر به دلیل استفاده از این ال سی جی ضعیف مورد سؤال قرار گرفته‌است.

سه خانواده رایج برای انتخاب پارامتر وجود دارد:

=== m اول، c = ۰ ===
{{اصلی|Lehmer random number generator}}
این ساخت و ساز اصلی لمر است. دوره است ''m''-1 اگر چند برابر ''a'' انتخاب شده‌است به یک عنصر بدوی از مدول اعداد صحیح ''m''. حالت اولیه باید بین ۱ و انتخاب شود ''m''−۱.

یکی از معایب مدول اصلی این است که کاهش مدولار به یک محصول دو عرض و یک مرحله کاهش صریح نیاز دارد. اغلب از یک عدد اول فقط کمتر از توان ۲ استفاده می‌شود ([[عدد اول مرسن|اعداد اول مرسن]] 2<sup>31</sup>−۱ و <sup>61</sup> 2−۱ محبوب هستند)، به طوری که مدول کاهش ''m'' = 2 <sup>''e''</sup> - ''d'' را می‌توان به صورت (''ax'' mod 2<sup>''e''</sup>) + ''d'' ⌊''ax''/2<sup>''e''</sup>⌋ اگر نتیجه خیلی زیاد است، باید با تفریق شرطی ''m'' دنبال شود، اما تعداد تفریق‌ها به ''ad'' / ''m'' محدود می‌شود، که اگر ''d'' کوچک باشد به راحتی می‌توان به یک محدود کرد.

اگر [[حاصل‌ضرب|حاصل ضرب]] دو عرض در دسترس نباشد و ضریب با دقت انتخاب شود، ممکن است '''از روش شراژ'''<ref>{{Cite web|title=Computer Systems Performance Analysis Chapter 26: Random-Number Generation|first=Raj|last=Jain|date=9 July 2010|pages=19–20|url=http://www.cse.wustl.edu/~jain/iucee/ftp/k_26rng.pdf#page=19|accessdate=2017-10-31}}</ref> استفاده شود. برای این کار، ''m'' را فاکتور کنید، یعنی ''m'' = ''qa''+''r'', i.e. ''q'' = ⌊''m''/''a''⌋ and ''r'' = ''m'' mod ''a''. سپس ''ax'' mod ''m'' = ''a''(''x'' mod ''q'') − ''r''⌊''x''/''q''⌋ را محاسبه کنید. از زمانی که ''x'' mod ''q'' < ''q'' ≤ ''m''/''a''، جمله اول به شدت کمتر از ''am''/''a'' = ''m است'' اگر ''a'' طوری انتخاب شود که ''r'' ≤ ''q'' (و بنابراین ''r'' / ''q'' ≤ ۱)، سپس جمله دوم نیز کمتر از ''m'' است: ''m'': ''r''⌊''x''/''q''⌋ ≤ ''rx''/''q'' = ''x''(''r''/''q'') ≤ ''x'' < ''m''. بنابراین، هر دو محصول را می‌توان با یک محصول تک عرض محاسبه کرد، و تفاوت بین آنها در محدوده [1- ''m'' , ''m'' -۱]، بنابراین می‌توان به [۰، ''m'' -1] با یک جمع شرطی منفرد.<ref>{{Cite web|title=Schrage's Method|url=http://home.earthlink.net/~pfenerty/pi/schrages_method.html|first=Paul|last=Fenerty|date=11 September 2006|accessdate=2017-10-31|archive-date=۹ ژوئیه ۲۰۱۶|archive-url=https://web.archive.org/web/20160709153256/http://home.earthlink.net/~pfenerty/pi/schrages_method.html|dead-url=yes}}</ref>

دومین عیب این است که تبدیل مقدار ۱≤x و ''m > x'' به بیت‌های تصادفی یکنواخت. اگر از یک عدد اول فقط کمتر از توان ۲ استفاده شود، گاهی اوقات مقادیر از دست رفته به سادگی نادیده گرفته می‌شوند.

=== m توان ۲، c = ۰ ===
انتخاب ''m'' به عنوان توان ۲، اغلب ''m'' = 2 <sup>32</sup> یا ''m'' = 2 <sup>64</sup>، یک L C G کارآمد تولید می‌کند، زیرا این امکان را فراهم می‌کند که عملیات مدول به سادگی با کوتاه کردن نمایش باینری محاسبه شود. در واقع، مهم‌ترین بیت‌ها معمولاً اصلاً محاسبه نمی‌شوند. با این حال، معایبی وجود دارد.

این فرم دارای حداکثر دوره ''m'' /4 است که اگر ''a'' ≡ 3 or ''a'' ≡ 5 (mod 8) به دست می‌آید. حالت اولیه ''X'' <sub>0</sub> باید فرد باشد و سه بیت پایین ''X'' بین دو حالت متناوب هستند و مفید نیستند. می‌توان نشان داد که این شکل معادل یک ژنراتور با مدول یک چهارم اندازه و ''c'' ≠ ۰ است {{R|KnuthV2}}

یک مسئله جدی تر در مورد استفاده از مدول توان دو این است که بیت‌های کم دوره کوتاه تری نسبت به بیت‌های بالا دارند. بیت پایین‌ترین مرتبه ''X'' هرگز تغییر نمی‌کند (''X'' همیشه فرد است)، و دو بیت بعدی بین دو حالت متناوب می‌شوند. اگر''a'' ≡ (5 mod ۸)، سپس بیت ۱ هرگز تغییر نمی‌کند و بیت ۲ جایگزین می‌شود. اگر''a'' ≡ 3 (mod 8)، سپس بیت ۲ هرگز تغییر نمی‌کند و بیت ۱ جایگزین می‌شود) بیت ۳ با پریود ۴ تکرار می‌شود، بیت ۴ دارای دوره ۸ است و به همین ترتیب. فقط مهم‌ترین بیت ''X'' به دوره کامل می‌رسد.

=== c ≠ ۰ ===
وقتی ''c'' ≠ ۰ باشد، پارامترهای به درستی انتخاب شده، دوره ای برابر با ''m'' را برای همه مقادیر دانه در نظر می‌گیرند. این اتفاق می‌افتد [[اگر و تنها اگر|اگر و فقط اگر]]: {{R|KnuthV2}}
# <math>m</math> و <math>c</math> [[اعداد متباین|نسبتا درجه یک]] هستند،
# <math>a - 1</math> بر تمام [[عدد اول|عوامل اول]] تقسیم پذیر است <math>m</math> ،
# <math>a - 1</math> بر ۴ بخش پذیر است اگر <math>m</math> بر ۴ بخش پذیر است.

به این سه شرط، قضیه هال-دوبل می‌گویند.<ref>{{Cite journal|last=Hull|first=T. E.|last2=Dobell|first2=A. R.|date=July 1962|title=Random Number Generators|url=http://chagall.med.cornell.edu/BioinfoCourse/PDFs/Lecture4/random_number_generator.pdf|journal=SIAM Review|volume=4|issue=3|pages=230–254|bibcode=1962SIAMR...4..230H|doi=10.1137/1004061|access-date=2016-06-26|hdl-access=free}}</ref>

این فرم ممکن است با هر ''m'' استفاده شود، اما فقط برای ''m'' با بسیاری از فاکتورهای اول مکرر، مانند توان ۲، به خوبی کار می‌کند. استفاده از [[کلمه (معماری رایانه)|اندازه کلمه]] کامپیوتر رایج‌ترین انتخاب است. اگر ''m'' یک عدد صحیح بدون مربع باشد، این فقط به ''a'' ≡ 1 (mod ''m'') اجازه می‌دهد که P R N G بسیار ضعیفی را ایجاد می‌کند. انتخابی از ضرب‌کننده‌های دوره کامل ممکن فقط زمانی در دسترس است که ''m'' دارای ضرایب اول مکرر باشد.

اگرچه قضیه هال-دوبل حداکثر دوره را ارائه می‌دهد، اما برای تضمین یک مولد ''خوب'' کافی نیست؛ مثلاً برای ''الف'' مطلوب است - ۱ بیش از حد لازم بر ضرایب اول ''m'' قابل تقسیم نباشد؛ بنابراین، اگر ''m'' توان ۲ باشد، ''a'' - 1 باید بر ۴ بخش پذیر باشد اما بر ۸ بخش پذیر نباشد، یعنیa ≡ 5 (Mod 8). {{R|KnuthV2}}

در واقع، بیشتر ضرب‌کننده‌ها دنباله‌ای را تولید می‌کنند که در یکی از آزمون‌های غیرتصادفی یا دیگری شکست می‌خورد، و ضربی را پیدا می‌کند که برای همه معیارهای قابل اجرا رضایت‌بخش باشد {{R|KnuthV2}} کاملاً چالش‌برانگیز است تست طیفی یکی از مهم‌ترین تست هاست.<ref name="Austin2008">{{Cite web|first=David|last=Austin|title=Random Numbers: Nothing Left to Chance|date=March 2008|publisher=American Mathematical Society|url=https://www.ams.org/publicoutreach/feature-column/fcarc-random}}</ref>

توجه داشته باشید که یک مدول توان-۲ مشکل را همان‌طور که در بالا برای ۰=''c'' توضیح داده شد به اشتراک می‌گذارد: بیت‌های ''k'' پایین یک ژنراتور با مدول 2<sup>''k''</sup> تشکیل می‌دهند و بنابراین با دوره 2<sup>''k''</sup> تکرار می‌شوند. فقط مهم‌ترین بیت به دوره کامل می‌رسد. اگر عدد شبه تصادفی کمتر از ''r'' مورد نظر باشد، ⌊''r X''/''m''⌋نتیجه با کیفیت بسیار بالاتری نسبت به ''X'' mod ''r'' می‌شود. متأسفانه، بیشتر زبان‌های برنامه‌نویسی نوشتن دومی را بسیار ساده‌تر می‌کنند (<code>X % r</code>)، بنابراین رایج‌ترین شکل مورد استفاده است.

ژنراتور به انتخاب ''c'' حساس ''نیست''، تا زمانی که نسبتاً اول مدول باشد (مثلاً اگر ''m'' توان ۲ باشد، ''c'' باید فرد باشد)، بنابراین مقدار ''c'' =۱ معمولاً انتخاب می‌شود.

سری تولید شده توسط سایر گزینه‌های ''c'' را می‌توان به عنوان یک تابع ساده از [[سری زمانی]] که ''c'' =۱ نوشت. {{R|KnuthV2}} به‌طور خاص، اگر ''Y''سری اولیه تعریف شده توسط ''Y''<sub>0</sub> = ۰ باشد و ''Y'' <sub>''n'' +1</sub> = ''a Y <sub>n</sub>'' +1 mod m، سپس یک سری کلی ''X<sub>n</sub>''<sub>+1</sub> = ''aX<sub>n</sub>''+''c'' mod ''m'' را می‌توان به عنوان یک تابع وابسته از ''Y'' نوشت:

: <math>X_n = (X_0(a-1)+c)Y_n + X_0 = (X_1 - X_0)Y_n + X_0 \pmod m.</math>

به‌طور کلی، هر دو سری ''X'' و ''Z'' با ضریب و مدول یکسان با هم مرتبط هستند

: <math>{ X_n - X_0 \over X_1 - X_0 } = Y_n = {a^n - 1 \over a - 1} = { Z_n - Z_0 \over Z_1 - Z_0 } \pmod m.</math>

== پارامترهای مورد استفاده رایج ==
جدول زیر پارامترهای L C Gهای رایج را فهرست می‌کند، از جمله توابع ()''rand'' داخلی در [[کتابخانه زمان اجرا|کتابخانه‌های زمان اجرا]] [[کامپایلر]]های مختلف. این جدول برای نشان دادن محبوبیت است، نه نمونه‌هایی برای تقلید. ''بسیاری از این پارامترها ضعیف هستند.'' جداول پارامترهای خوب موجود است. {{R|LEcuyer99|Steele20}}
{| class="wikitable"
!Source
!modulus
''m''
!multiplier
''a''
|-
|''[[:en:ZX81|ZX81]]''
|2<sup>16</sup> + ۱
|۷۵
|-
|''[[:en:Numerical Recipes|Numerical Recipes]]''
|2<sup>32</sup>
|۱۶۶۴۵۲۵
|-
|[[:en:Borland|Borland]] C/C++
|2<sup>32</sup>
|۲۲۶۹۵۴۷۷
|-
|[[:en:Glibc|glibc]] (used by [[:en:GNU Compiler Collection|GCC]])<ref>{{یادکرد وب |نشانی=https://sourceware.org/git/?p=glibc.git%3Ba%3Dblob%3Bf%3Dstdlib%2Frandom_r.c%3Bhb%3Dglibc-2.26#l362 |عنوان=Implementation in glibc-2.26 release. |بازبینی=۲۴ ژوئن ۲۰۲۲ |archive-date=۲۶ فوریه ۲۰۲۱ |archive-url=https://web.archive.org/web/20210226211536/https://sourceware.org/git/?p=glibc.git%3Ba%3Dblob%3Bf%3Dstdlib%2Frandom_r.c%3Bhb%3Dglibc-2.26#l362 |dead-url=yes }}</ref>
|2<sup>31</sup>
|۱۱۰۳۵۱۵۲۴۵
|-
|[[:en:ANSI C|ANSI C]]: [[:en:Watcom C compiler|Watcom]], [[:en:Digital Mars|Digital Mars]], [[:en:CodeWarrior|CodeWarrior]], [[:en:IBM VisualAge|IBM VisualAge]] C/C++<ref>{{cite book|title=A collection of selected pseudorandom number generators with linear structures|author=K. Entacher|date=21 August 1997|url=http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.53.3686&rep=rep1&type=pdf|access-date=16 June 2012|citeseerx=10.1.1.53.3686}}</ref>
[[:en:C90 (C version)|C90]], [[:en:C99|C99]], [[:en:C11 (C standard revision)|C11]]: Suggestion in the ISO/IEC 9899,<ref>{{cite web|title=Last public Committee Draft from April 12, 2011|page=346f|url=http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf|access-date=21 Dec 2014}}</ref> [[:en:C17 (C standard revision)|C17]]
|2<sup>31</sup>
|۱۱۰۳۵۱۵۲۴۵
|-
|[[:en:Borland Delphi|Borland Delphi]], [[:en:Virtual Pascal|Virtual Pascal]]
|2<sup>32</sup>
|۱۳۴۷۷۵۸۱۳
|-
|[[:en:Turbo Pascal|Turbo Pascal]]
|2<sup>32</sup>
|134775813 (8088405<sub>16</sub>)
|-
|[[:en:Visual C++|Microsoft Visual/Quick C/C++]]
|2<sup>32</sup>
|214013 (343FD<sub>16</sub>)
|-
|[[:en:Visual Basic|Microsoft Visual Basic]] (6 and earlier)<ref>{{cite web|title=How Visual Basic Generates Pseudo-Random Numbers for the RND Function|url=http://support.microsoft.com/kb/231847|publisher=Microsoft|access-date=17 June 2011|archive-url=https://web.archive.org/web/20110417000838/http://support.microsoft.com/kb/231847|archive-date=۱۷ آوریل ۲۰۱۱|dead-url=yes|date=24 June 2004}}</ref>
|{{math|''2''<sup>''24''</sup>}}
|1140671485 (43FD43FD<sub>16</sub>)
|-
|RtlUniform from [[:en:Native API|Native API]]<ref>In spite of documentation on [http://msdn.microsoft.com/en-us/library/bb432429(VS.85).aspx MSDN], RtlUniform uses LCG, and not Lehmer's algorithm, implementations before [[Windows Vista]] are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied</ref>
|1 - 2<sup>31</sup>
|2147483629 (7FFFFFED<sub>16</sub>)
|-
|[[:en:CarbonLib|Apple CarbonLib]], [[:en:C++11|C++11]]'s <code>minstd_rand0</code>,<ref name="cpp11">{{cite web|title=ISO/IEC 14882:2011|publisher=ISO|date=2 September 2011|url=http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=50372|access-date=3 September 2011}}</ref> MATLAB's v4 legacy generator mcg16807<ref>{{cite web|title=Creating and Controlling a Random Number Stream|publisher=MathWorks|url=https://www.mathworks.com/help/matlab/math/creating-and-controlling-a-random-number-stream.html|access-date=7 June 2021}}</ref>
|1 - 2<sup>31</sup>
|۱۶۸۰۷
|-
|[[:en:C++11|C++11]]'s <code>minstd_rand</code><ref name="cpp11"/>
|1 - 2<sup>31</sup>
|۴۸۲۷۱
|-
|[[:en:MMIX|MMIX]] by [[:en:Donald Knuth|Donald Knuth]]
|2<sup>64</sup>
|۶۳۶۴۱۳۶۲۲۳۸۴۶۷۹۳۰۰۵
|-
|[[:en:Newlib|Newlib]], [[:en:Musl|Musl]]
|2<sup>64</sup>
|۶۳۶۴۱۳۶۲۲۳۸۴۶۷۹۳۰۰۵
|-
|[[:en:OpenVMS|VMS]]'s '''MTH$RANDOM''',<ref>{{cite web|url=https://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html|title=GNU Scientific Library: Other random number generators}}</ref> old versions of [[:en:Glibc|glibc]]
|2<sup>32</sup>
|69069 (10DCD<sub>16</sub>)
|-
|[[:en:Java (programming language)|Java]]'s java.util{{Not a typo|.}}Random, [[:en:POSIX|POSIX]] [ln]rand48, [[:en:Glibc|glibc]] [ln]rand48[_r]
|2<sup>48</sup>
|25214903917 (5DEECE66D<sub>16</sub>)
|-
|<code>random0</code><ref name="Stephen J. Chapman">Stephen J. Chapman.</ref><ref name="Stephen J. Chapman"/><ref name="Stephen J. Chapman"/><ref>S. J. Chapman. [http://www.udel.edu/CIS/106/pconrad/MPE3/code/chap5/random0.m random0]. 2004.</ref><ref>Wu-ting Tsai.</ref>
|134456 = 2<sup>3</sup>7<sup>5</sup>
|۸۱۲۱
|-
|[[:en:POSIX|POSIX]]<ref>[http://pubs.opengroup.org/onlinepubs/9699919799/ The Open Group Base Specifications Issue 7] IEEE Std 1003.1, 2013 Edition</ref> [jm]rand48, [[:en:Glibc|glibc]] [mj]rand48[_r]
|2<sup>48</sup>
|25214903917 (5DEECE66D<sub>16</sub>)
|-
|[[:en:POSIX|POSIX]] [de]rand48, [[:en:Glibc|glibc]] [de]rand48[_r]
|2<sup>48</sup>
|25214903917 (5DEECE66D<sub>16</sub>)
|-
|[[:en:Cc65|cc65]]<ref>{{cite web|first=Sidney|last=Cadot|url=https://github.com/cc65/cc65/blob/master/libsrc/common/rand.s|title=rand.s|work=cc65|access-date=8 July 2016}}</ref>
|2<sup>23</sup>
|65793 (10101<sub>16</sub>)
|-
|[[:en:Cc65|cc65]]
|2<sup>32</sup>
|16843009 (1010101<sub>16</sub>)
|-
|''Formerly common:'' {{midsize|[[RANDU]]}}<ref name="Press2">{{cite book|last=Press|first=William H.|year=1992|title=Numerical Recipes in Fortran 77: The Art of Scientific Computing|edition=2nd|isbn=978-0-521-43064-7|display-authors=etal|title-link=Numerical Recipes}}</ref>
|2<sup>31</sup>
|۶۵۵۳۹
|}
همان‌طور که در بالا نشان داده شد، L C Gها همیشه از همه بیت‌ها در مقادیری که تولید می‌کنند استفاده نمی‌کنند. به عنوان مثال، پیاده‌سازی [[جاوا]] با مقادیر ۴۸ بیتی در هر تکرار عمل می‌کند اما تنها ۳۲ بیت مهم آن را برمی‌گرداند. این به این دلیل است که بیت‌های مرتبه بالاتر دوره‌های طولانی تری نسبت به بیت‌های مرتبه پایین دارند (به زیر مراجعه کنید). L C Gهایی که از این تکنیک برش استفاده می‌کنند از نظر آماری مقادیر بهتری نسبت به آنهایی که استفاده نمی‌کنند تولید می‌کنند. این امر به ویژه در اسکریپت‌هایی که از عملیات mod برای کاهش دامنه استفاده می‌کنند قابل توجه است. تغییر شماره تصادفی mod 2 منجر به جایگزینی ۰ و ۱ بدون برش می‌شود.

== مزایا و معایب ==
L C Gها سریع هستند و برای حفظ حالت به حداقل حافظه (یک عدد ''مدولو-م''، اغلب ۳۲ یا ۶۴ بیت) نیاز دارند. این باعث می‌شود آنها برای شبیه‌سازی چندین جریان مستقل ارزشمند باشند. L C Gها برای برنامه‌های رمزنگاری در نظر گرفته نشده‌اند و نباید استفاده شوند. از یک [[مولد امن اعداد شبه‌تصادفی در رمزنگاری|تولیدکننده اعداد شبه تصادفی امن رمزنگاری]] برای چنین برنامه‌هایی استفاده کنید.
[[پرونده:Lcg_3d.gif|بندانگشتی|200x200پیکسل| [[ابرصفحه]]‌های یک ژنراتور همگام خطی در سه بعدی. این ساختار همان چیزی است که تست طیفی اندازه‌گیری می‌کند.]]
اگرچه L C Gها دارای چند ضعف خاص هستند، اما بسیاری از ایرادات آن‌ها ناشی از داشتن حالت بسیار کوچک است. این واقعیت که مردم برای سال‌های متمادی برای استفاده از آن‌ها با چنین مدول‌های کوچکی دلسرد شده‌اند، می‌تواند به عنوان شاهدی بر قدرت این تکنیک در نظر گرفته شود. یک L C G با حالت به اندازه کافی بزرگ می‌تواند حتی تست‌های آماری سخت گیرانه را نیز پشت سر بگذارد. یک L C G modulo-2 که ۳۲ بیت بالا را برمی‌گرداند، مجموعه Small Crush TestU01 را پاس می‌کند.{{مدرک|date=November 2017|reason=O'Neill stated this result somewhere, but I'm having a hard time finding it.}} و یک L C G (۹۶ بیتی) سخت‌گیرانه‌ترین مجموعه Big Crush را پشت سر می‌گذارد.

برای مثالی خاص، انتظار می‌رود که یک مولد اعداد تصادفی ایده‌آل با خروجی ۳۲ بیت (با [[مسئله تاریخ تولد|قضیه تولد]]) شروع به تکثیر خروجی‌های قبلی پس از نتایج ''m'' ≈ 2<sup>۱۶√</sup> کند. ''هر'' P R N G که خروجی آن حالت کامل و ناقص است، تا زمانی که دوره کامل آن سپری نشود، موارد تکراری تولید نمی‌کند، که یک نقص آماری به راحتی قابل تشخیص است. به دلایل مرتبط، هر P R N G باید دوره ای بیشتر از مجذور تعداد خروجی‌های مورد نیاز داشته باشد. با توجه به سرعت کامپیوترهای مدرن، این به معنای یک دوره 2<sup>64</sup> برای همه برنامه‌ها به جز کم‌تقاضا، و طولانی‌تر برای شبیه‌سازی‌های سخت است.

یکی از ایرادهای خاص L C Gها این است که، اگر برای انتخاب نقاط در فضای n بعدی استفاده شود، نقاط حداکثر روی [[ابرصفحه]]‌های {{رادیکال|''n''!⋅''m''|''n''}} قرار می‌گیرند (قضیه مارسالیا، که توسط جورج مارسالیا ایجاد شده‌است).<ref name="Marsaglia68">{{Cite journal|last=Marsaglia|first=George|author-link=George Marsaglia|date=September 1968|title=Random Numbers Fall Mainly in the Planes|url=https://www.pnas.org/content/61/1/25.full.pdf|journal=[[PNAS]]|volume=61|issue=1|pages=25–28|bibcode=1968PNAS...61...25M|doi=10.1073/pnas.61.1.25|pmc=285899|pmid=16591687|doi-access=free}}</ref> این به دلیل همبستگی سریال بین مقادیر متوالی دنباله ''X <sub>n</sub>'' است. ضریب‌هایی که با دقت انتخاب شده‌اند معمولاً صفحات بسیار کمتری دارند که فاصله زیادی دارند، که می‌تواند منجر به مشکلات شود. تست طیفی، که یک آزمایش ساده از کیفیت L C G است، این فاصله را اندازه‌گیری می‌کند و اجازه می‌دهد تا یک ضرب‌کننده خوب انتخاب شود.

فاصله صفحه هم به مدول و هم به ضریب بستگی دارد. یک مدول به اندازه کافی بزرگ می‌تواند این فاصله را کمتر از وضوح اعداد با دقت مضاعف کاهش دهد. انتخاب ضریب زمانی که مدول بزرگ باشد اهمیت کمتری پیدا می‌کند. هنوز هم لازم است که شاخص طیفی را محاسبه کنیم و مطمئن شویم که ضریب بد نیست، اما به‌طور کاملاً احتمالی، زمانی که مدول بزرگتر از حدود 2<sup>64</sup> باشد، احتمال برخورد با ضریب بد بسیار کم می‌شود.

یکی دیگر از عیب‌های خاص L C Gها، دوره کوتاه بیت‌های مرتبه پایین است که ''m'' به عنوان توان ۲ انتخاب می‌شود. این را می‌توان با استفاده از مدول بزرگتر از خروجی مورد نیاز و استفاده از مهم‌ترین بیت‌های حالت کاهش داد.

با این وجود، برای برخی از کاربردها L C G ممکن است گزینه خوبی باشد. به عنوان مثال، در یک سیستم تعبیه شده، مقدار حافظه در دسترس اغلب به شدت محدود است. به‌طور مشابه، در محیطی مانند یک [[کنسول بازی ویدئویی|کنسول بازی ویدیویی]]، گرفتن تعداد کمی از بیت‌های درجه بالا از یک L C G ممکن است کافی باشد. (بیت‌های مرتبه پایین L C Gها وقتی m توان ۲ است هرگز نباید برای هیچ درجه ای از تصادفی بودن به آنها اعتماد کرد) بیت‌های مرتبه پایین چرخه‌های بسیار کوتاهی را طی می‌کنند. به‌طور خاص، هر L C G چرخه کامل، زمانی که m توان ۲ باشد، به‌طور متناوب نتایج زوج و فرد ایجاد می‌کند.

L C Gها باید از نظر مناسب بودن در کاربردهای غیر رمزنگاری که در آنها [[اعداد تصادفی|تصادفی بودن]] با کیفیت بالا حیاتی است، بسیار دقیق ارزیابی شوند. برای شبیه‌سازی مونت کارلو، یک L C G باید از مدول بزرگ‌تر و ترجیحاً بسیار بیشتر از مکعب تعداد نمونه‌های تصادفی مورد نیاز استفاده کند. این بدان معناست که برای مثال می‌توان از یک L C G ۳۲بیتی (خوب) برای بدست آوردن حدود هزار عدد تصادفی استفاده کرد. یک L C G (۶۴بیتی) برای حدود ۲۲۱ نمونه تصادفی (کمی بیش از دو میلیون) و غیره مناسب است. به همین دلیل، در عمل L C Gها برای شبیه‌سازی‌های مونت کارلو در مقیاس بزرگ مناسب نیستند.

== کد نمونه ==
=== کد پایتون ===
در زیر پیاده‌سازی L C G در [[پایتون (زبان برنامه‌نویسی)|پایتون]] به شکل [[مولد (برنامه‌نویسی)|ژنراتور]] آمده‌است:<syntaxhighlight lang="python">
from typing import Generator

def lcg(modulus: int, a: int, c: int, seed: int) -> Generator[int, None, None]:
    """Linear congruential generator."""
    while True:
        seed = (a * seed + c) % modulus
        yield seed
</syntaxhighlight>

=== پاسکال رایگان ===
رایگان پاسکال با استفاده از یک مرسن تویستر به عنوان مولد عدد شبه تصادفی پیش فرض خود را در حالی که دلفی با استفاده از یک ال سی جی. در اینجا یک مثال سازگار دلفی در زبان پاسکال بر اساس اطلاعات موجود در جدول بالاست. با توجه به همان مقدار دانه رند همان توالی اعداد تصادفی دلفی را تولید می‌کند.<syntaxhighlight lang="pascal">
unit lcg_random;
{$ifdef fpc}{$mode delphi}{$endif}
interface

function LCGRandom: extended; overload; inline;
function LCGRandom(const range:longint): longint; overload; inline;

implementation
function IM: cardinal; inline;
begin
  RandSeed := RandSeed * 134775813 + 1;
  Result := RandSeed;
end;

function LCGRandom: extended; overload; inline;
begin
  Result := IM * 2.32830643653870e-10;
end;

function LCGRandom(const range: longint): longint; overload; inline;
begin
  Result := IM * range shr 32;
end;</syntaxhighlight>مانند همه مولدهای اعداد شبه تصادفی، یک L C G باید وضعیت را ذخیره کند و هر بار که یک عدد جدید تولید می‌کند، آن را تغییر دهد. ممکن است چندین رشته به‌طور همزمان به این حالت دسترسی پیدا کنند و باعث ایجاد شرایط مسابقه شوند. پیاده‌سازی‌ها باید از حالت‌های متفاوتی استفاده کنند که هر کدام با مقداردهی اولیه منحصربه‌فرد برای رشته‌های مختلف استفاده کنند تا از دنباله‌های مساوی از اعداد تصادفی در رشته‌هایی که به‌طور همزمان اجرا می‌شوند اجتناب شود.

== مشتقات L C G ==
ژنراتورهای متعددی وجود دارند که ژنراتورهای متجانس خطی به شکل متفاوتی هستند و بنابراین تکنیک‌های مورد استفاده برای تجزیه و تحلیل L C Gها را می‌توان برای آنها به کار برد.

یکی از روش‌های تولید یک دوره طولانی‌تر است به‌طور خلاصه خروجی چند ال سی جی از دوره‌های مختلف داشتن یک بزرگ [[کوچک‌ترین مضرب مشترک|حداقل مضرب مشترک]]; این ویچمن-هیل ژنراتور نمونه ای از این فرم است. (ما ترجیح می‌دهیم که به‌طور کامل باشد [[اعداد متباین|کوپریم]]، اما یک مدول نخست حاکی از یک دوره حتی، بنابراین باید یک عامل مشترک وجود داشته باشد ۲, حداقل) این را می‌توان معادل یک ال سی جی منفرد با یک مدول برابر با محصول مدول ال سی جی مولفه نشان داد.

P R N Gهای اضافه کردن با حمل و تفریق با قرض گرفتن مارسالیا با اندازه کلمه ''b'' = 2 <sup>''w''</sup> و تأخیر ''r'' و ''s'' (''r'' > ''s'') معادل L C G با مدول ''b <sup>r</sup>'' ± ''b <sup>s</sup>'' ± ۱ هستند.

P R N Gهای ضرب با حمل با ضریب ''a'' معادل L C Gهایی با مدول اول بزرگ ''ab <sup>r</sup>'' -1 و [[ضریب توان]] ۲ ''b'' هستند.

یک ژنراتور همخوانی جابجا شده با یک L C G توان ۲ مدول شروع می‌شود و یک تبدیل خروجی را برای حذف مشکل دوره کوتاه در بیت‌های مرتبه پایین اعمال می‌کند.

== مقایسه با سایر P R N Gها ==
بدوی دیگر که به‌طور گسترده برای به دست آوردن توالی‌های شبه تصادفی طولانی مدت استفاده می‌شود، ساخت [[ثبات تغییر بازخورد خطی|رجیستر تغییر بازخورد خطی]] است که بر اساس محاسبات در G F(2)[''x'']، [[حلقه چندجمله‌ای|حلقه چند جمله ای]] بر روی G F(2) است. به جای جمع و ضرب اعداد صحیح، عملیات اصلی ضرب [[یای انحصاری|منحصر به فرد یا بدون]] حمل است که معمولاً به صورت دنباله ای از [[شیفت منطقی|جابجایی‌های منطقی]] اجرا می‌شود. اینها این مزیت را دارند که تمام بیت‌های آنها تمام دوره هستند. آنها از ضعف بیت‌های مرتبه پایین که مدول حسابی 2<sup>''k''</sup> را آزار می‌دهد، رنج نمی‌برند.

نمونه‌هایی از این خانواده عبارتند از ژنراتورهای xor-shift و چرخش مرسن. دومی یک دوره بسیار طولانی (1- 2<sup>19937</sup>) و یکنواختی متغیر را ارائه می‌دهد، اما در برخی آزمون‌های آماری شکست می‌خورد.<ref>{{Cite journal|last=Matsumoto|first=Makoto|last2=Nishimura|first2=Takuji|date=January 1998|title=Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator|url=https://pdfs.semanticscholar.org/098d/5792ffa43e9885f9fc644ffdd7b6a59b0922.pdf|journal=ACM Transactions on Modeling and Computer Simulation|volume=8|issue=1|pages=3–30|citeseerx=10.1.1.215.1141|doi=10.1145/272991.272995|archive-url=https://web.archive.org/web/20171107004909/https://pdfs.semanticscholar.org/098d/5792ffa43e9885f9fc644ffdd7b6a59b0922.pdf|archive-date=2017-11-07}}</ref> ژنراتورهای فیبوناچی عقب مانده نیز در این دسته قرار می‌گیرند. اگرچه آنها از جمع حسابی استفاده می‌کنند، دوره آنها توسط یک L F S R در میان بیت‌های کم‌اهمیت تضمین می‌شود.

تشخیص ساختار یک رجیستر تغییر بازخورد خطی با تست‌های مناسب<ref name="rfc4086">{{Cite IETF|title=Randomness Requirements for Security|date=June 2005}}</ref> مانند تست پیچیدگی خطی اجرا شده در مجموعه TestU01 آسان است. یک ماتریس گردشی بولی که از بیت‌های متوالی یک L F S R مقداردهی می‌شود هرگز [[رتبه (جبر خطی)|رتبه]] ای بیشتر از درجه چند جمله ای نخواهد داشت. افزودن یک تابع اختلاط خروجی غیرخطی (مانند ساختارهای**xoshiro256 و ژنراتور متجانس تغییر یافته) می‌تواند عملکرد در آزمایش‌های آماری را تا حد زیادی بهبود بخشد.

ساختار دیگر برای P R N G یک تابع بازگشتی بسیار ساده است که با یک تابع اختلاط خروجی قدرتمند ترکیب شده‌است. این شامل رمزهای بلوک [[مدهای کاری رمزهای قطعه‌ای|حالت شمارنده]] و مولدهای غیر رمزنگاری مانند [http://prng.di.unimi.it/splitmix64.c SplitMix64] است.

ساختاری شبیه به L C Gها، اما ''نه'' معادل، مولد چند بازگشتی است: ''X <sub>n</sub>'' = (''a'' <sub>1</sub> ''X'' <sub>''n'' -1</sub> + ''a'' <sub>2</sub> ''X'' <sub>''n'' -2</sub> + ··· + ''a <sub>k</sub> X'' <sub>''n'' − ''k''</sub>) mod ''m'' برای ''k'' ≥ ۲. با مدول اول، این می‌تواند دوره‌هایی تا ''m <sup>k</sup>''−۱ ایجاد کند، بنابراین توسعه مفید ساختار L C G به دوره‌های بزرگ‌تر است.

یک تکنیک قدرتمند برای تولید اعداد شبه تصادفی با کیفیت بالا، ترکیب دو یا چند P R N G با ساختار متفاوت است. مجموع یک L F S R و یک L C G (مانند ساختارهای KISS یا xor-wow) می‌تواند با هزینه ای در سرعت بسیار خوب عمل کند.

== جستارهای وابسته ==
* فهرست مولدهای اعداد تصادفی - سایر P R N Gها از جمله برخی با کیفیت‌های آماری بهتر
* ژنراتور ACORN - نباید با A C G اشتباه گرفته شود که به نظر می‌رسد برای انواع ژنراتورهای L C G و L F S R استفاده شده‌است.
* ژنراتور همگام تغییر یافته
* چرخه کامل
* مولد همگام معکوس
* ضرب با حمل
* لمر- R N G (گاهی اوقات پارک–میلر R N G نامیده می‌شود)
* مولد همگرای خطی ترکیبی

== یادداشت‌ها ==
== منابع ==
{{پانویس}}
** {{Citation|last1=Press|first1=WH|last2=Teukolsky|first2=SA|last3=Vetterling|first3=WT|last4=Flannery|first4=BP|year=2007|title=Numerical Recipes: The Art of Scientific Computing|edition=3rd|publisher=Cambridge University Press|location=New York|isbn=978-0-521-88068-8|chapter=Section 7.1.1. Some History|chapter-url=http://apps.nrbook.com/empanel/index.html#pg=343}}
** Gentle, James E. , (2003). ''Random Number Generation and Monte Carlo Methods'', 2nd edition, Springer, {{ISBN|0-387-00178-6}}.
** {{cite journal|author=Joan Boyar|year=1989|title=Inferring sequences produced by pseudo-random number generators|url=http://asterix.cs.gsu.edu/crypto/p129-boyar.pdf|journal=[[Journal of the ACM]]|volume=36|issue=1|pages=129–141|doi=10.1145/58562.59305|s2cid=3565772}} (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).

== پیوند به بیرون ==
** The simulation [http://www.vias.org/simulations/simusoft_lincong.html Linear Congruential Generator] visualizes the correlations between the pseudo-random numbers when manipulating the parameters.
** [https://web.archive.org/web/20081211083300/http://www.cs.virginia.edu/~rjg7v/annotated.html Security of Random Number Generation: An Annotated Bibliography]
** [https://web.archive.org/web/20090108194540/http://www.math.niu.edu/~rusin/known-math/99/LCG Linear Congruential Generators post to sci.math]
** [http://www.goldsteintech.com/art.php The "Death of Art" computer art project at Goldstein Technologies LLC, uses an LCG to generate 33,554,432 images]
** P. L'Ecuyer and R. Simard, [http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf "TestU01: A C Library for Empirical Testing of Random Number Generators"], May 2006, revised November 2006, ''ACM Transactions on Mathematical Software'', 33, 4, Article 22, August 2007.
** [https://web.archive.org/web/20150616223328/http://yurichev.com/blog/modulo/ Article about another way of cracking LCG]

[[رده:حساب پیمانه‌ای]]
[[رده:مقاله‌های دارای کد نمونه به زبان پایتون]]
[[رده:مولدهای عدد شبه‌تصادفی]]