مولد همگرایانه خطی کیست؟ توضیح بده.
یک مولد همگام خطی (L C G) الگوریتمی است که دنباله ای از اعداد شبه تصادفی محاسبه شده با یک معادله خطی تکه ای ناپیوسته را به دست می‌دهد. این روش یکی از قدیمی‌ترین و شناخته شده‌ترین الگوریتم‌های مولد اعداد شبه تصادفی را نشان می‌دهد. تئوری پشت آن‌ها نسبتاً آسان است و به راحتی و سریع پیاده‌سازی می‌شوند، مخصوصاً روی سخت‌افزار رایانه که می‌تواند محاسبات مدولار را با برش بیت ذخیره‌سازی ارائه دهد.مولد با رابطه عود تعریف می‌شود:جایی که formula_2 دنباله ای از مقادیر شبه تصادفی است وثابت‌های صحیحی هستند که مولد را مشخص می‌کنند. اگر "c" = ۰، مولد اغلب یک مولد همگام ضربی نامیده می‌شود. اگرc ≠ ۰، این روش را یک مولد متجانس مختلط می‌نامند. زمانی که "c" ≠ ۰، یک ریاضیدان عود را تبدیلی وابسته می‌نامد، نه یک تبدیل خطی، اما این نام اشتباه در علم کامپیوتر به خوبی تثبیت شده‌است. تاریخ.ژنراتور لمر در سال ۱۹۵۱ منتشر شد و ژنراتور همخوانی خطی در سال ۱۹۵۸ توسط دبلیو ای تامسون و ای. روتنبرگ منتشر شد.طول دوره.یکی از مزایای ال سی جی‌ها این است که انتخاب مناسب پارامترها منجر به یک دوره شناخته شده و طولانی می‌شود. اگر چه نه تنها معیار، بیش از حد کوتاه یک دوره یک نقص کشنده در یک مولد عدد شبه تصادفی است.در حالی که ال سی جی‌ها قادر به تولید هستند اعداد شبه تصادفی که می‌تواند رسمی باشد تست‌های تصادفی، کیفیت خروجی به انتخاب پارامترها بسیار حساس است "m" و "a". به عنوان مثال، "a" = ۱ و "c" = ۱ یک مدول ساده تولید می‌کند-"m" شمارنده، که دارای یک دوره طولانی، اما واضح است که غیر تصادفی است.از لحاظ تاریخی انتخاب‌های ضعیف برای "a" به پیاده‌سازی بی اثر از ال سی جی منجر شده‌است. یک مثال به خصوص گویا از این است راندو که به‌طور گسترده‌ای در اوایل دهه ۱۹۷۰ مورد استفاده قرار گرفت و منجر به نتایج بسیاری شد که در حال حاضر به دلیل استفاده از این ال سی جی ضعیف مورد سؤال قرار گرفته‌است.سه خانواده رایج برای انتخاب پارامتر وجود دارد:m اول، c = ۰.این ساخت و ساز اصلی لمر است. دوره است "m"-1 اگر چند برابر "a" انتخاب شده‌است به یک عنصر بدوی از مدول اعداد صحیح "m". حالت اولیه باید بین ۱ و انتخاب شود "m"−۱.یکی از معایب مدول اصلی این است که کاهش مدولار به یک محصول دو عرض و یک مرحله کاهش صریح نیاز دارد. اغلب از یک عدد اول فقط کمتر از توان ۲ استفاده می‌شود (اعداد اول مرسن 231−۱ و 61 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" &lt; "q" ≤ "m"/"a"، جمله اول به شدت کمتر از "am"/"a" = "m است" اگر "a" طوری انتخاب شود که "r" ≤ "q" (و بنابراین "r" / "q" ≤ ۱)، سپس جمله دوم نیز کمتر از "m" است: "m": "r"⌊"x"/"q"⌋ ≤ "rx"/"q" = "x"("r"/"q") ≤ "x" &lt; "m". بنابراین، هر دو محصول را می‌توان با یک محصول تک عرض محاسبه کرد، و تفاوت بین آنها در محدوده [1- "m" , "m" -۱]، بنابراین می‌توان به [۰، "m" -1] با یک جمع شرطی منفرد.دومین عیب این است که تبدیل مقدار ۱≤x و "m &gt; x" به بیت‌های تصادفی یکنواخت. اگر از یک عدد اول فقط کمتر از توان ۲ استفاده شود، گاهی اوقات مقادیر از دست رفته به سادگی نادیده گرفته می‌شوند.m توان ۲، c = ۰.انتخاب "m" به عنوان توان ۲، اغلب "m" = 2 32 یا "m" = 2 64، یک L C G کارآمد تولید می‌کند، زیرا این امکان را فراهم می‌کند که عملیات مدول به سادگی با کوتاه کردن نمایش باینری محاسبه شود. در واقع، مهم‌ترین بیت‌ها معمولاً اصلاً محاسبه نمی‌شوند. با این حال، معایبی وجود دارد.این فرم دارای حداکثر دوره "m" /4 است که اگر "a" ≡ 3 or "a" ≡ 5 (mod 8) به دست می‌آید. حالت اولیه "X" 0 باید فرد باشد و سه بیت پایین "X" بین دو حالت متناوب هستند و مفید نیستند. می‌توان نشان داد که این شکل معادل یک ژنراتور با مدول یک چهارم اندازه و "c" ≠ ۰ است یک مسئله جدی تر در مورد استفاده از مدول توان دو این است که بیت‌های کم دوره کوتاه تری نسبت به بیت‌های بالا دارند. بیت پایین‌ترین مرتبه "X" هرگز تغییر نمی‌کند ("X" همیشه فرد است)، و دو بیت بعدی بین دو حالت متناوب می‌شوند. اگر"a" ≡ (5 mod ۸)، سپس بیت ۱ هرگز تغییر نمی‌کند و بیت ۲ جایگزین می‌شود. اگر"a" ≡ 3 (mod 8)، سپس بیت ۲ هرگز تغییر نمی‌کند و بیت ۱ جایگزین می‌شود) بیت ۳ با پریود ۴ تکرار می‌شود، بیت ۴ دارای دوره ۸ است و به همین ترتیب. فقط مهم‌ترین بیت "X" به دوره کامل می‌رسد.c ≠ ۰.وقتی "c" ≠ ۰ باشد، پارامترهای به درستی انتخاب شده، دوره ای برابر با "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" می‌شود. متأسفانه، بیشتر زبان‌های برنامه‌نویسی نوشتن دومی را بسیار ساده‌تر می‌کنند (codice_1)، بنابراین رایج‌ترین شکل مورد استفاده است.ژنراتور به انتخاب "c" حساس "نیست"، تا زمانی که نسبتاً اول مدول باشد (مثلاً اگر "m" توان ۲ باشد، "c" باید فرد باشد)، بنابراین مقدار "c" =۱ معمولاً انتخاب می‌شود.سری تولید شده توسط سایر گزینه‌های "c" را می‌توان به عنوان یک تابع ساده از سری زمانی که "c" =۱ نوشت. به‌طور خاص، اگر "Y"سری اولیه تعریف شده توسط "Y"0 = ۰ باشد و "Y" "n" +1 = "a Y n" +1 mod m، سپس یک سری کلی "Xn"+1 = "aXn"+"c" mod "m" را می‌توان به عنوان یک تابع وابسته از "Y" نوشت:به‌طور کلی، هر دو سری "X" و "Z" با ضریب و مدول یکسان با هم مرتبط هستندپارامترهای مورد استفاده رایج.جدول زیر پارامترهای L C Gهای رایج را فهرست می‌کند، از جمله توابع ()"rand" داخلی در کتابخانه‌های زمان اجرا کامپایلرهای مختلف. این جدول برای نشان دادن محبوبیت است، نه نمونه‌هایی برای تقلید. "بسیاری از این پارامترها ضعیف هستند." جداول پارامترهای خوب موجود است. همان‌طور که در بالا نشان داده شد، 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 باید دوره ای بیشتر از مجذور تعداد خروجی‌های مورد نیاز داشته باشد. با توجه به سرعت کامپیوترهای مدرن، این به معنای یک دوره 264 برای همه برنامه‌ها به جز کم‌تقاضا، و طولانی‌تر برای شبیه‌سازی‌های سخت است.یکی از ایرادهای خاص L C Gها این است که، اگر برای انتخاب نقاط در فضای n بعدی استفاده شود، نقاط حداکثر روی ابرصفحه‌های قرار می‌گیرند (قضیه مارسالیا، که توسط جورج مارسالیا ایجاد شده‌است). این به دلیل همبستگی سریال بین مقادیر متوالی دنباله "X n" است. ضریب‌هایی که با دقت انتخاب شده‌اند معمولاً صفحات بسیار کمتری دارند که فاصله زیادی دارند، که می‌تواند منجر به مشکلات شود. تست طیفی، که یک آزمایش ساده از کیفیت L C G است، این فاصله را اندازه‌گیری می‌کند و اجازه می‌دهد تا یک ضرب‌کننده خوب انتخاب شود.فاصله صفحه هم به مدول و هم به ضریب بستگی دارد. یک مدول به اندازه کافی بزرگ می‌تواند این فاصله را کمتر از وضوح اعداد با دقت مضاعف کاهش دهد. انتخاب ضریب زمانی که مدول بزرگ باشد اهمیت کمتری پیدا می‌کند. هنوز هم لازم است که شاخص طیفی را محاسبه کنیم و مطمئن شویم که ضریب بد نیست، اما به‌طور کاملاً احتمالی، زمانی که مدول بزرگتر از حدود 264 باشد، احتمال برخورد با ضریب بد بسیار کم می‌شود.یکی دیگر از عیب‌های خاص 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 Generatordef lcg(modulus: int, a: int, c: int, seed: int) -&gt; Generator[int, None, None]: """Linear congruential generator.""" while True: seed = (a * seed + c) % modulus yield seedپاسکال رایگان.رایگان پاسکال با استفاده از یک مرسن تویستر به عنوان مولد عدد شبه تصادفی پیش فرض خود را در حالی که دلفی با استفاده از یک ال سی جی. در اینجا یک مثال سازگار دلفی در زبان پاسکال بر اساس اطلاعات موجود در جدول بالاست. با توجه به همان مقدار دانه رند همان توالی اعداد تصادفی دلفی را تولید می‌کند.unit lcg_random;interfacefunction LCGRandom: extended; overload; inline;function LCGRandom(const range:longint): longint; overload; inline;implementationfunction 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" &gt; "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- 219937) و یکنواختی متغیر را ارائه می‌دهد، اما در برخی آزمون‌های آماری شکست می‌خورد. ژنراتورهای فیبوناچی عقب مانده نیز در این دسته قرار می‌گیرند. اگرچه آنها از جمع حسابی استفاده می‌کنند، دوره آنها توسط یک L F S R در میان بیت‌های کم‌اهمیت تضمین می‌شود.تشخیص ساختار یک رجیستر تغییر بازخورد خطی با تست‌های مناسب مانند تست پیچیدگی خطی اجرا شده در مجموعه TestU01 آسان است. یک ماتریس گردشی بولی که از بیت‌های متوالی یک L F S R مقداردهی می‌شود هرگز رتبه ای بیشتر از درجه چند جمله ای نخواهد داشت. افزودن یک تابع اختلاط خروجی غیرخطی (مانند ساختارهای**xoshiro256 و ژنراتور متجانس تغییر یافته) می‌تواند عملکرد در آزمایش‌های آماری را تا حد زیادی بهبود بخشد.ساختار دیگر برای P R N G یک تابع بازگشتی بسیار ساده است که با یک تابع اختلاط خروجی قدرتمند ترکیب شده‌است. این شامل رمزهای بلوک حالت شمارنده و مولدهای غیر رمزنگاری مانند SplitMix64 است.ساختاری شبیه به L C Gها، اما "نه" معادل، مولد چند بازگشتی است: "X n" = ("a" 1 "X" "n" -1 + "a" 2 "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) می‌تواند با هزینه ای در سرعت بسیار خوب عمل کند.