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

دو LCG مدولو-۹ نشان می‌دهد که چگونه پارامترهای مختلف منجر به طول چرخه‌های مختلف می‌شود. هر ردیف وضعیت را نشان می‌دهد که در حال تکامل است تا زمانی که تکرار شود. ردیف بالا یک ژنراتور با m را نشان می‌دهد = ۹، الف = ۲، ج = ۰ و دانه ۱ که چرخه ای به طول ۶ ایجاد می‌کند. ردیف دوم همان ژنراتور با دانه ۳ است که یک چرخه به طول ۲ تولید می‌کند. با استفاده از a = ۴ و ج = ۱ (ردیف پایین) طول چرخه ۹ را با هر دانه در [۰، ۸].

یک مولد همگام خطی (L C G) الگوریتمی است که دنباله ای از اعداد شبه تصادفی محاسبه شده با یک معادله خطی تکه ای ناپیوسته را به دست می‌دهد. این روش یکی از قدیمی‌ترین و شناخته شده‌ترین الگوریتم‌های مولد اعداد شبه تصادفی را نشان می‌دهد. تئوری پشت آن‌ها نسبتاً آسان است و به راحتی و سریع پیاده‌سازی می‌شوند، مخصوصاً روی سخت‌افزار رایانه که می‌تواند محاسبات مدولار را با برش بیت ذخیره‌سازی ارائه دهد.

مولد با رابطه عود تعریف می‌شود:

$X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}$

جایی که $X$ دنباله ای از مقادیر شبه تصادفی است و

$m,\,0<m$ - " مدول "

$a,\,0<a<m$ - "ضریب"

$c,\,0\leq c<m$ - "افزایش"

$X_{0},\,0\leq X_{0}<m$ - "seed" یا "start value"

ثابت‌های صحیحی هستند که مولد را مشخص می‌کنند. اگر c = ۰، مولد اغلب یک مولد همگام ضربی نامیده می‌شود. اگرc ≠ ۰، این روش را یک مولد متجانس مختلط می‌نامند.

زمانی که c ≠ ۰، یک ریاضیدان عود را تبدیلی وابسته می‌نامد، نه یک تبدیل خطی، اما این نام اشتباه در علم کامپیوتر به خوبی تثبیت شده‌است.

تاریخ

ژنراتور لمر در سال ۱۹۵۱ منتشر شد و ژنراتور همخوانی خطی در سال ۱۹۵۸ توسط دبلیو ای تامسون و ای. روتنبرگ منتشر شد.

طول دوره

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

در حالی که ال سی جی‌ها قادر به تولید هستند اعداد شبه تصادفی که می‌تواند رسمی باشد تست‌های تصادفی، کیفیت خروجی به انتخاب پارامترها بسیار حساس است m و a. به عنوان مثال، a = ۱ و c = ۱ یک مدول ساده تولید می‌کند-m شمارنده، که دارای یک دوره طولانی، اما واضح است که غیر تصادفی است.

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

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

m اول، c = ۰

مقالهٔ اصلی: Lehmer random number generator

این ساخت و ساز اصلی لمر است. دوره است m-1 اگر چند برابر a انتخاب شده‌است به یک عنصر بدوی از مدول اعداد صحیح m. حالت اولیه باید بین ۱ و انتخاب شود m−۱.

یکی از معایب مدول اصلی این است که کاهش مدولار به یک محصول دو عرض و یک مرحله کاهش صریح نیاز دارد. اغلب از یک عدد اول فقط کمتر از توان ۲ استفاده می‌شود (اعداد اول مرسن 2³¹−۱ و ⁶¹ 2−۱ محبوب هستند)، به طوری که مدول کاهش m = 2 ^e - d را می‌توان به صورت (ax mod 2^e) + d ⌊ax/2^e⌋ اگر نتیجه خیلی زیاد است، باید با تفریق شرطی m دنبال شود، اما تعداد تفریق‌ها به ad / m محدود می‌شود، که اگر d کوچک باشد به راحتی می‌توان به یک محدود کرد.

اگر حاصل ضرب دو عرض در دسترس نباشد و ضریب با دقت انتخاب شود، ممکن است از روش شراژ استفاده شود. برای این کار، 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] با یک جمع شرطی منفرد.

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

m توان ۲، c = ۰

انتخاب m به عنوان توان ۲، اغلب m = 2 ³² یا m = 2 ⁶⁴، یک L C G کارآمد تولید می‌کند، زیرا این امکان را فراهم می‌کند که عملیات مدول به سادگی با کوتاه کردن نمایش باینری محاسبه شود. در واقع، مهم‌ترین بیت‌ها معمولاً اصلاً محاسبه نمی‌شوند. با این حال، معایبی وجود دارد.

این فرم دارای حداکثر دوره m /4 است که اگر a ≡ 3 or a ≡ 5 (mod 8) به دست می‌آید. حالت اولیه X ₀ باید فرد باشد و سه بیت پایین X بین دو حالت متناوب هستند و مفید نیستند. می‌توان نشان داد که این شکل معادل یک ژنراتور با مدول یک چهارم اندازه و c ≠ ۰ است

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

c ≠ ۰

وقتی c ≠ ۰ باشد، پارامترهای به درستی انتخاب شده، دوره ای برابر با m را برای همه مقادیر دانه در نظر می‌گیرند. این اتفاق می‌افتد اگر و فقط اگر:

1. $m$ و $c$ نسبتا درجه یک هستند،
2. $a-1$ بر تمام عوامل اول تقسیم پذیر است $m$ ،
3. $a-1$ بر ۴ بخش پذیر است اگر $m$ بر ۴ بخش پذیر است.

به این سه شرط، قضیه هال-دوبل می‌گویند.

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

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

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

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

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

سری تولید شده توسط سایر گزینه‌های c را می‌توان به عنوان یک تابع ساده از سری زمانی که c =۱ نوشت. به‌طور خاص، اگر Yسری اولیه تعریف شده توسط Y₀ = ۰ باشد و Y _{n +1} = a Y _n +1 mod m، سپس یک سری کلی X_n+1 = aX_n+c mod m را می‌توان به عنوان یک تابع وابسته از Y نوشت:

$X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}.$

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

${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}}.$

پارامترهای مورد استفاده رایج

جدول زیر پارامترهای L C Gهای رایج را فهرست می‌کند، از جمله توابع ()rand داخلی در کتابخانه‌های زمان اجرا کامپایلرهای مختلف. این جدول برای نشان دادن محبوبیت است، نه نمونه‌هایی برای تقلید. بسیاری از این پارامترها ضعیف هستند. جداول پارامترهای خوب موجود است.

Source	modulus m	multiplier a
ZX81	216 + ۱	۷۵
Numerical Recipes	232	۱۶۶۴۵۲۵
Borland C/C++	232	۲۲۶۹۵۴۷۷
glibc (used by GCC)	231	۱۱۰۳۵۱۵۲۴۵
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ C90, C99, C11: Suggestion in the ISO/IEC 9899, C17	231	۱۱۰۳۵۱۵۲۴۵
Borland Delphi, Virtual Pascal	232	۱۳۴۷۷۵۸۱۳
Turbo Pascal	232	134775813 (808840516)
Microsoft Visual/Quick C/C++	232	214013 (343FD16)
Microsoft Visual Basic (6 and earlier)	224	1140671485 (43FD43FD16)
RtlUniform from Native API	1 - 231	2147483629 (7FFFFFED16)
Apple CarbonLib, C++11's minstd_rand0, MATLAB's v4 legacy generator mcg16807	1 - 231	۱۶۸۰۷
C++11's minstd_rand	1 - 231	۴۸۲۷۱
MMIX by Donald Knuth	264	۶۳۶۴۱۳۶۲۲۳۸۴۶۷۹۳۰۰۵
Newlib, Musl	264	۶۳۶۴۱۳۶۲۲۳۸۴۶۷۹۳۰۰۵
VMS's MTH$RANDOM, old versions of glibc	232	69069 (10DCD16)
Java's java.util.Random, POSIX [ln]rand48, glibc [ln]rand48[_r]	248	25214903917 (5DEECE66D16)
random0	134456 = 2375	۸۱۲۱
POSIX [jm]rand48, glibc [mj]rand48[_r]	248	25214903917 (5DEECE66D16)
POSIX [de]rand48, glibc [de]rand48[_r]	248	25214903917 (5DEECE66D16)
cc65	223	65793 (1010116)
cc65	232	16843009 (101010116)
Formerly common: RANDU	231	۶۵۵۳۹

همان‌طور که در بالا نشان داده شد، L C Gها همیشه از همه بیت‌ها در مقادیری که تولید می‌کنند استفاده نمی‌کنند. به عنوان مثال، پیاده‌سازی جاوا با مقادیر ۴۸ بیتی در هر تکرار عمل می‌کند اما تنها ۳۲ بیت مهم آن را برمی‌گرداند. این به این دلیل است که بیت‌های مرتبه بالاتر دوره‌های طولانی تری نسبت به بیت‌های مرتبه پایین دارند (به زیر مراجعه کنید). L C Gهایی که از این تکنیک برش استفاده می‌کنند از نظر آماری مقادیر بهتری نسبت به آنهایی که استفاده نمی‌کنند تولید می‌کنند. این امر به ویژه در اسکریپت‌هایی که از عملیات mod برای کاهش دامنه استفاده می‌کنند قابل توجه است. تغییر شماره تصادفی mod 2 منجر به جایگزینی ۰ و ۱ بدون برش می‌شود.

مزایا و معایب

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

ابرصفحه‌های یک ژنراتور همگام خطی در سه بعدی. این ساختار همان چیزی است که تست طیفی اندازه‌گیری می‌کند.

اگرچه L C Gها دارای چند ضعف خاص هستند، اما بسیاری از ایرادات آن‌ها ناشی از داشتن حالت بسیار کوچک است. این واقعیت که مردم برای سال‌های متمادی برای استفاده از آن‌ها با چنین مدول‌های کوچکی دلسرد شده‌اند، می‌تواند به عنوان شاهدی بر قدرت این تکنیک در نظر گرفته شود. یک L C G با حالت به اندازه کافی بزرگ می‌تواند حتی تست‌های آماری سخت گیرانه را نیز پشت سر بگذارد. یک L C G modulo-2 که ۳۲ بیت بالا را برمی‌گرداند، مجموعه Small Crush TestU01 را پاس می‌کند. و یک L C G (۹۶ بیتی) سخت‌گیرانه‌ترین مجموعه Big Crush را پشت سر می‌گذارد.

برای مثالی خاص، انتظار می‌رود که یک مولد اعداد تصادفی ایده‌آل با خروجی ۳۲ بیت (با قضیه تولد) شروع به تکثیر خروجی‌های قبلی پس از نتایج m ≈ 2^۱۶√ کند. هر P R N G که خروجی آن حالت کامل و ناقص است، تا زمانی که دوره کامل آن سپری نشود، موارد تکراری تولید نمی‌کند، که یک نقص آماری به راحتی قابل تشخیص است. به دلایل مرتبط، هر P R N G باید دوره ای بیشتر از مجذور تعداد خروجی‌های مورد نیاز داشته باشد. با توجه به سرعت کامپیوترهای مدرن، این به معنای یک دوره 2⁶⁴ برای همه برنامه‌ها به جز کم‌تقاضا، و طولانی‌تر برای شبیه‌سازی‌های سخت است.

یکی از ایرادهای خاص L C Gها این است که، اگر برای انتخاب نقاط در فضای n بعدی استفاده شود، نقاط حداکثر روی ابرصفحه‌های ⁿ√n!⋅m قرار می‌گیرند (قضیه مارسالیا، که توسط جورج مارسالیا ایجاد شده‌است). این به دلیل همبستگی سریال بین مقادیر متوالی دنباله X _n است. ضریب‌هایی که با دقت انتخاب شده‌اند معمولاً صفحات بسیار کمتری دارند که فاصله زیادی دارند، که می‌تواند منجر به مشکلات شود. تست طیفی، که یک آزمایش ساده از کیفیت L C G است، این فاصله را اندازه‌گیری می‌کند و اجازه می‌دهد تا یک ضرب‌کننده خوب انتخاب شود.

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

یکی دیگر از عیب‌های خاص 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 در پایتون به شکل ژنراتور آمده‌است:

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

پاسکال رایگان

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

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;

مانند همه مولدهای اعداد شبه تصادفی، یک L C G باید وضعیت را ذخیره کند و هر بار که یک عدد جدید تولید می‌کند، آن را تغییر دهد. ممکن است چندین رشته به‌طور همزمان به این حالت دسترسی پیدا کنند و باعث ایجاد شرایط مسابقه شوند. پیاده‌سازی‌ها باید از حالت‌های متفاوتی استفاده کنند که هر کدام با مقداردهی اولیه منحصربه‌فرد برای رشته‌های مختلف استفاده کنند تا از دنباله‌های مساوی از اعداد تصادفی در رشته‌هایی که به‌طور همزمان اجرا می‌شوند اجتناب شود.

مشتقات L C G

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

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

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

P R N Gهای ضرب با حمل با ضریب a معادل L C Gهایی با مدول اول بزرگ ab ^r -1 و ضریب توان ۲ b هستند.

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

مقایسه با سایر P R N Gها

بدوی دیگر که به‌طور گسترده برای به دست آوردن توالی‌های شبه تصادفی طولانی مدت استفاده می‌شود، ساخت رجیستر تغییر بازخورد خطی است که بر اساس محاسبات در G F(2)[x]، حلقه چند جمله ای بر روی G F(2) است. به جای جمع و ضرب اعداد صحیح، عملیات اصلی ضرب منحصر به فرد یا بدون حمل است که معمولاً به صورت دنباله ای از جابجایی‌های منطقی اجرا می‌شود. اینها این مزیت را دارند که تمام بیت‌های آنها تمام دوره هستند. آنها از ضعف بیت‌های مرتبه پایین که مدول حسابی 2^k را آزار می‌دهد، رنج نمی‌برند.

نمونه‌هایی از این خانواده عبارتند از ژنراتورهای xor-shift و چرخش مرسن. دومی یک دوره بسیار طولانی (1- 2¹⁹⁹³⁷) و یکنواختی متغیر را ارائه می‌دهد، اما در برخی آزمون‌های آماری شکست می‌خورد. ژنراتورهای فیبوناچی عقب مانده نیز در این دسته قرار می‌گیرند. اگرچه آنها از جمع حسابی استفاده می‌کنند، دوره آنها توسط یک L F S R در میان بیت‌های کم‌اهمیت تضمین می‌شود.

تشخیص ساختار یک رجیستر تغییر بازخورد خطی با تست‌های مناسب مانند تست پیچیدگی خطی اجرا شده در مجموعه TestU01 آسان است. یک ماتریس گردشی بولی که از بیت‌های متوالی یک L F S R مقداردهی می‌شود هرگز رتبه ای بیشتر از درجه چند جمله ای نخواهد داشت. افزودن یک تابع اختلاط خروجی غیرخطی (مانند ساختارهای**xoshiro256 و ژنراتور متجانس تغییر یافته) می‌تواند عملکرد در آزمایش‌های آماری را تا حد زیادی بهبود بخشد.

ساختار دیگر برای P R N G یک تابع بازگشتی بسیار ساده است که با یک تابع اختلاط خروجی قدرتمند ترکیب شده‌است. این شامل رمزهای بلوک حالت شمارنده و مولدهای غیر رمزنگاری مانند SplitMix64 است.

ساختاری شبیه به L C Gها، اما نه معادل، مولد چند بازگشتی است: X _n = (a ₁ X _{n -1} + a ₂ X _{n -2} + ··· + a _k X _{n − k}) mod m برای k ≥ ۲. با مدول اول، این می‌تواند دوره‌هایی تا m ^k−۱ ایجاد کند، بنابراین توسعه مفید ساختار 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 نامیده می‌شود)
• مولد همگرای خطی ترکیبی

منابع

• • Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 7.1.1. Some History", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
  • Gentle, James E. , (2003). Random Number Generation and Monte Carlo Methods, 2nd edition, Springer, شابک ‎۰−۳۸۷−۰۰۱۷۸−۶.
  • Joan Boyar (1989). "Inferring sequences produced by pseudo-random number generators" (PDF). Journal of the ACM. 36 (1): 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 Linear Congruential Generator visualizes the correlations between the pseudo-random numbers when manipulating the parameters.
  • Security of Random Number Generation: An Annotated Bibliography
  • Linear Congruential Generators post to sci.math
  • 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, "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.
  • Article about another way of cracking LCG