موضوع مقاله: مولد همگرایانه خطی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مولد همگرایانه خطی | مقدمه: ردیف بالا یک ژنراتور با m را نشان می‌دهد = ۹، الف = ۲، ج = ۰ و دانه ۱ که چرخه ای به طول ۶ ایجاد می‌کند. | ## بخش 1: مولد همگرایانه خطی | یک مولد همگام خطی (L C G) الگوریتمی است که دنباله ای از اعداد شبه تصادفی محاسبه شده با یک معادله خطی تکه ای ناپیوسته را به دست می‌دهد. این روش یکی از قدیمی‌ترین و شناخته شده‌ترین الگوریتم‌های مولد اعداد شبه تصادفی را نشان می‌دهد. تئوری پشت آن‌ها نسبتاً آسان است و به راحتی و سریع پیاده‌سازی می‌شوند، مخصوصاً روی سخت‌افزار رایانه که می‌تواند محاسبات مدولار را با برش بیت ذخیره‌سازی ارائه دهد. مولد با رابطه عود تعریف می‌شود: جایی که دنباله ای از مقادیر شبه تصادفی است و - " مدول " - "ضریب" - "افزایش" - "seed" یا "start value" ثابت‌های صحیحی هستند که مولد را مشخص می‌کنند. زمانی که c ≠ ۰، یک ریاضیدان عود را تبدیلی وابسته می‌نامد، نه یک تبدیل خطی، اما این نام اشتباه در علم کامپیوتر به خوبی تثبیت شده‌است. تاریخ ژنراتور لمر در سال ۱۹۵۱ منتشر شد و ژنراتور همخوانی خطی در سال ۱۹۵۸ توسط دبلیو ای تامسون و ای. طول دوره یکی از مزایای ال سی جی‌ها این است که انتخاب مناسب پارامترها منجر به یک دوره شناخته شده و طولانی می‌شود. اگر چه نه تنها معیار، بیش از حد کوتاه یک دوره یک نقص کشنده در یک مولد عدد شبه تصادفی است. در حالی که ال سی جی‌ها قادر به تولید هستند اعداد شبه تصادفی که می‌تواند رسمی باشد تست‌های تصادفی، کیفیت خروجی به انتخاب پارامترها بسیار حساس است m و a. به عنوان مثال، a = ۱ و c = ۱ یک مدول ساده تولید می‌کند-m شمارنده، که دارای یک دوره طولانی، اما واضح است که غیر تصادفی است. از لحاظ تاریخی انتخاب‌های ضعیف برای a به پیاده‌سازی بی اثر از ال سی جی منجر شده‌است. یک مثال به خصوص گویا از این است راندو که به‌طور گسترده‌ای در اوایل دهه ۱۹۷۰ مورد استفاده قرار گرفت و منجر به نتایج بسیاری شد که در حال حاضر به دلیل استفاده از این ال سی جی ضعیف مورد سؤال قرار گرفته‌است. سه خانواده رایج برای انتخاب پارامتر وجود دارد: m اول، c = ۰ این ساخت و ساز اصلی لمر است. دوره است m-1 اگر چند برابر a انتخاب شده‌است به یک عنصر بدوی از مدول اعداد صحیح m. یکی از معایب مدول اصلی این است که کاهش مدولار به یک محصول دو عرض و یک مرحله کاهش صریح نیاز دارد. اغلب از یک عدد اول فقط کمتر از توان ۲ استفاده می‌شود (اعداد اول مرسن 231−۱ و 61 2−۱ محبوب هستند)، به طوری که مدول کاهش m = 2 e - d را می‌توان به صورت (ax mod 2e) + d ⌊ax/2e⌋ اگر نتیجه خیلی زیاد است، باید با تفریق شرطی m دنبال شود، اما تعداد تفریق‌ها به ad / m محدود می‌شود، که اگر d کوچک باشد به راحتی می‌توان به یک محدود کرد. اگر حاصل ضرب دو عرض در دسترس نباشد و ضریب با دقت انتخاب شود، ممکن است از روش شراژ استفاده شود. بنابراین، هر دو محصول را می‌توان با یک محصول تک عرض محاسبه کرد، و تفاوت بین آنها در محدوده [1- m , m -۱]، بنابراین می‌توان به [۰، m -1] با یک جمع شرطی منفرد. اگر از یک عدد اول فقط کمتر از توان ۲ استفاده شود، گاهی اوقات مقادیر از دست رفته به سادگی نادیده گرفته می‌شوند. m توان ۲، c = ۰ انتخاب m به عنوان توان ۲، اغلب m = 2 32 یا m = 2 64، یک L C G کارآمد تولید می‌کند، زیرا این امکان را فراهم می‌کند که عملیات مدول به سادگی با کوتاه کردن نمایش باینری محاسبه شود. حالت اولیه X 0 باید فرد باشد و سه بیت پایین X بین دو حالت متناوب هستند و مفید نیستند. می‌توان نشان داد که این شکل معادل یک ژنراتور با مدول یک چهارم اندازه و c ≠ ۰ است یک مسئله جدی تر در مورد استفاده از مدول توان دو این است که بیت‌های کم دوره کوتاه تری نسبت به بیت‌های بالا دارند. بیت پایین‌ترین مرتبه X هرگز تغییر نمی‌کند (X همیشه فرد است)، و دو بیت بعدی بین دو حالت متناوب می‌شوند. اگرa ≡ 3 (mod 8)، سپس بیت ۲ هرگز تغییر نمی‌کند و بیت ۱ جایگزین می‌شود) بیت ۳ با پریود ۴ تکرار می‌شود، بیت ۴ دارای دوره ۸ است و به همین ترتیب. c ≠ ۰ وقتی c ≠ ۰ باشد، پارامترهای به درستی انتخاب شده، دوره ای برابر با m را برای همه مقادیر دانه در نظر می‌گیرند. این اتفاق می‌افتد اگر و فقط اگر: و نسبتا درجه یک هستند، بر تمام عوامل اول تقسیم پذیر است ، بر ۴ بخش پذیر است اگر بر ۴ بخش پذیر است. این فرم ممکن است با هر m استفاده شود، اما فقط برای m با بسیاری از فاکتورهای اول مکرر، مانند توان ۲، به خوبی کار می‌کند. | ## بخش 2: مولد همگرایانه خطی | انتخابی از ضرب‌کننده‌های دوره کامل ممکن فقط زمانی در دسترس است که m دارای ضرایب اول مکرر باشد. اگرچه قضیه هال-دوبل حداکثر دوره را ارائه می‌دهد، اما برای تضمین یک مولد خوب کافی نیست؛ مثلاً برای الف مطلوب است - ۱ بیش از حد لازم بر ضرایب اول m قابل تقسیم نباشد؛ بنابراین، اگر m توان ۲ باشد، a - 1 باید بر ۴ بخش پذیر باشد اما بر ۸ بخش پذیر نباشد، یعنیa ≡ 5 (Mod 8). در واقع، بیشتر ضرب‌کننده‌ها دنباله‌ای را تولید می‌کنند که در یکی از آزمون‌های غیرتصادفی یا دیگری شکست می‌خورد، و ضربی را پیدا می‌کند که برای همه معیارهای قابل اجرا رضایت‌بخش باشد کاملاً چالش‌برانگیز است تست طیفی یکی از مهم‌ترین تست هاست. توجه داشته باشید که یک مدول توان-۲ مشکل را همان‌طور که در بالا برای ۰=c توضیح داده شد به اشتراک می‌گذارد: بیت‌های k پایین یک ژنراتور با مدول 2k تشکیل می‌دهند و بنابراین با دوره 2k تکرار می‌شوند. متأسفانه، بیشتر زبان‌های برنامه‌نویسی نوشتن دومی را بسیار ساده‌تر می‌کنند (X % r)، بنابراین رایج‌ترین شکل مورد استفاده است. ژنراتور به انتخاب c حساس نیست، تا زمانی که نسبتاً اول مدول باشد (مثلاً اگر m توان ۲ باشد، c باید فرد باشد)، بنابراین مقدار c =۱ معمولاً انتخاب می‌شود. سری تولید شده توسط سایر گزینه‌های c را می‌توان به عنوان یک تابع ساده از سری زمانی که c =۱ نوشت. به عنوان مثال، پیاده‌سازی جاوا با مقادیر ۴۸ بیتی در هر تکرار عمل می‌کند اما تنها ۳۲ بیت مهم آن را برمی‌گرداند. این به این دلیل است که بیت‌های مرتبه بالاتر دوره‌های طولانی تری نسبت به بیت‌های مرتبه پایین دارند (به زیر مراجعه کنید). L C Gهایی که از این تکنیک برش استفاده می‌کنند از نظر آماری مقادیر بهتری نسبت به آنهایی که استفاده نمی‌کنند تولید می‌کنند. این امر به ویژه در اسکریپت‌هایی که از عملیات mod برای کاهش دامنه استفاده می‌کنند قابل توجه است. مزایا و معایب L C Gها سریع هستند و برای حفظ حالت به حداقل حافظه (یک عدد مدولو-م، اغلب ۳۲ یا ۶۴ بیت) نیاز دارند. از یک تولیدکننده اعداد شبه تصادفی امن رمزنگاری برای چنین برنامه‌هایی استفاده کنید. اگرچه L C Gها دارای چند ضعف خاص هستند، اما بسیاری از ایرادات آن‌ها ناشی از داشتن حالت بسیار کوچک است. این واقعیت که مردم برای سال‌های متمادی برای استفاده از آن‌ها با چنین مدول‌های کوچکی دلسرد شده‌اند، می‌تواند به عنوان شاهدی بر قدرت این تکنیک در نظر گرفته شود. یک L C G با حالت به اندازه کافی بزرگ می‌تواند حتی تست‌های آماری سخت گیرانه را نیز پشت سر بگذارد. برای مثالی خاص، انتظار می‌رود که یک مولد اعداد تصادفی ایده‌آل با خروجی ۳۲ بیت (با قضیه تولد) شروع به تکثیر خروجی‌های قبلی پس از نتایج m ≈ 2۱۶√ کند. هر P R N G که خروجی آن حالت کامل و ناقص است، تا زمانی که دوره کامل آن سپری نشود، موارد تکراری تولید نمی‌کند، که یک نقص آماری به راحتی قابل تشخیص است. به دلایل مرتبط، هر P R N G باید دوره ای بیشتر از مجذور تعداد خروجی‌های مورد نیاز داشته باشد. با توجه به سرعت کامپیوترهای مدرن، این به معنای یک دوره 264 برای همه برنامه‌ها به جز کم‌تقاضا، و طولانی‌تر برای شبیه‌سازی‌های سخت است. یکی از ایرادهای خاص L C Gها این است که، اگر برای انتخاب نقاط در فضای n بعدی استفاده شود، نقاط حداکثر روی ابرصفحه‌های قرار می‌گیرند (قضیه مارسالیا، که توسط جورج مارسالیا ایجاد شده‌است). ضریب‌هایی که با دقت انتخاب شده‌اند معمولاً صفحات بسیار کمتری دارند که فاصله زیادی دارند، که می‌تواند منجر به مشکلات شود. تست طیفی، که یک آزمایش ساده از کیفیت L C G است، این فاصله را اندازه‌گیری می‌کند و اجازه می‌دهد تا یک ضرب‌کننده خوب انتخاب شود. یک مدول به اندازه کافی بزرگ می‌تواند این فاصله را کمتر از وضوح اعداد با دقت مضاعف کاهش دهد. هنوز هم لازم است که شاخص طیفی را محاسبه کنیم و مطمئن شویم که ضریب بد نیست، اما به‌طور کاملاً احتمالی، زمانی که مدول بزرگتر از حدود 264 باشد، احتمال برخورد با ضریب بد بسیار کم می‌شود. یکی دیگر از عیب‌های خاص L C Gها، دوره کوتاه بیت‌های مرتبه پایین است که m به عنوان توان ۲ انتخاب می‌شود. این را می‌توان با استفاده از مدول بزرگتر از خروجی مورد نیاز و استفاده از مهم‌ترین بیت‌های حالت کاهش داد. | ## بخش 3: مولد همگرایانه خطی | به عنوان مثال، در یک سیستم تعبیه شده، مقدار حافظه در دسترس اغلب به شدت محدود است. به‌طور مشابه، در محیطی مانند یک کنسول بازی ویدیویی، گرفتن تعداد کمی از بیت‌های درجه بالا از یک 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 ژنراتورهای متعددی وجود دارند که ژنراتورهای متجانس خطی به شکل متفاوتی هستند و بنابراین تکنیک‌های مورد استفاده برای تجزیه و تحلیل L C Gها را می‌توان برای آنها به کار برد. یکی از روش‌های تولید یک دوره طولانی‌تر است به‌طور خلاصه خروجی چند ال سی جی از دوره‌های مختلف داشتن یک بزرگ حداقل مضرب مشترک; این ویچمن-هیل ژنراتور نمونه ای از این فرم است. (ما ترجیح می‌دهیم که به‌طور کامل باشد کوپریم، اما یک مدول نخست حاکی از یک دوره حتی، بنابراین باید یک عامل مشترک وجود داشته باشد ۲, حداقل) این را می‌توان معادل یک ال سی جی منفرد با یک مدول برابر با محصول مدول ال سی جی مولفه نشان داد. یک ژنراتور همخوانی جابجا شده با یک L C G توان ۲ مدول شروع می‌شود و یک تبدیل خروجی را برای حذف مشکل دوره کوتاه در بیت‌های مرتبه پایین اعمال می‌کند. مقایسه با سایر P R N Gها بدوی دیگر که به‌طور گسترده برای به دست آوردن توالی‌های شبه تصادفی طولانی مدت استفاده می‌شود، ساخت رجیستر تغییر بازخورد خطی است که بر اساس محاسبات در G F(2 x]، حلقه چند جمله ای بر روی G F(2) است. به جای جمع و ضرب اعداد صحیح، عملیات اصلی ضرب منحصر به فرد یا بدون حمل است که معمولاً به صورت دنباله ای از جابجایی‌های منطقی اجرا می‌شود. دومی یک دوره بسیار طولانی (1- 219937) و یکنواختی متغیر را ارائه می‌دهد، اما در برخی آزمون‌های آماری شکست می‌خورد. اگرچه آنها از جمع حسابی استفاده می‌کنند، دوره آنها توسط یک L F S R در میان بیت‌های کم‌اهمیت تضمین می‌شود. تشخیص ساختار یک رجیستر تغییر بازخورد خطی با تست‌های مناسب مانند تست پیچیدگی خطی اجرا شده در مجموعه TestU01 آسان است. یک ماتریس گردشی بولی که از بیت‌های متوالی یک L F S R مقداردهی می‌شود هرگز رتبه ای بیشتر از درجه چند جمله ای نخواهد داشت. افزودن یک تابع اختلاط خروجی غیرخطی (مانند ساختارهای**xoshiro256 و ژنراتور متجانس تغییر یافته) می‌تواند عملکرد در آزمایش‌های آماری را تا حد زیادی بهبود بخشد. ساختار دیگر برای P R N G یک تابع بازگشتی بسیار ساده است که با یک تابع اختلاط خروجی قدرتمند ترکیب شده‌است. با مدول اول، این می‌تواند دوره‌هایی تا m k−۱ ایجاد کند، بنابراین توسعه مفید ساختار L C G به دوره‌های بزرگ‌تر است. | ## جمع‌بندی | یک تکنیک قدرتمند برای تولید اعداد شبه تصادفی با کیفیت بالا، ترکیب دو یا چند P R N G با ساختار متفاوت است.