تولید اعداد تصادفی با Mersenne Twister – الگوریتم و مفاهیم اولیه | به زبان ساده

«اعداد تصادفی» (Random Number) و همچنین اعداد «شبه تصادفی» (Pseudo Random) در صنعت، نمونه‌گیری و توزیع‌های آماری و بخصوص در «رمزنگاری» (Cryptography) اطلاعات رایانه‌ای کاربرد دارند. الگوریتم و روش‌های مختلفی برای تولید اعداد شبه تصادفی وجود دارد که یکی از مرسوم ترین آن‌ها روش تولید اعداد تصادفی با Mersenne Twister یا الگوریتم Mersenne Twister است. به علت پرکاربرد بودن این تکنیک در بسیاری از نرم‌افزارهای رایانه‌ای، در این متن به معرفی تکنیک تولید اعداد تصادفی به روش Mersenne Twister می‌پردازیم. در انتها نیز دو بخش برای معرفی این الگوریتم با استفاده از شبه کد و همچنین کد پایتون اشاره خواهیم کرد.

تولید اعداد تصادفی با Mersenne Twister

«مرسن پیچشی» «Mersenne Twister» یک تولید کننده «اعداد شبه تصادفی» (Pseudo Random Number Generator) یا به اختصار PRNG است. روش‌های مبتنی بر PRNG بیشترین کاربرد عمومی در تولید اعداد (شبه) تصادفی را دارد. نام روش تولید اعداد تصادفی با Mersenne Twister از این واقعیت ناشی می‌شود که طول دوره تناوب آن به عنوان یک «عدد اول مرسن» (Mersenne prime) انتخاب شده است.

فیلم مجموعه آموزش برنامه نویسی پایتون Python – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

Mersenne Twister در سال 1997 توسط دو دانشمند ژاپنی به نام‌های «ماکوتو ماتسومو» (Makoto Matsumoto) و «تاکوجی ناشیمورا» (Takuji Nishimura) ابداع گشت. این روش به طور خاص برای رفع بسیاری از نقایص موجود در روش‌های قدیمی مولد اعداد شبه تصادفی طراحی شده است.

متداولترین نسخه الگوریتم Mersenne Twister براساس Mersenne prime 219937−1 ساخته شده است. در اجرای نسخه استاندارد آن، یعنی MT19937، از کلمه با طول 32 بیت استفاده می‌شود. پیاده سازی دیگری نیز وجود دارد که از کلمه با طول 64 بیت، MT19937-64 استفاده می‌کند. این الگوریتم توالی متفاوتی نسبت به الگوریتم ۳۲ بیتی ایجاد می‌کند. عبارت MT مخفف Mersenne Twister است. به همین دلیل در ادامه متن هرگاه بخواهیم به مرسن پیچشی اشاره کنیم از خلاصه آن یعنی MT بهره می‌گیریم.

کاربرد در سیستم‌های نرم افزاری

همچنین MT PRNG در Apache Commons، در ++C استاندارد (از C ++ 11) و Mathematica نیز موجود است. پیاده سازی این الگوریتم در بسیاری از کتابخانه‌های برنامه‌ها از جمله Boost C ++ Libraries، کتابخانه CUDA، و کتابخانه عددی NAG ارائه شده است.

مرسن پیچشی، یکی از دو دو روش تولید اعداد تصادفی در نرم‌افزار SPSS نیز هست. در حقیقت روش دیگر در این نرم‌افزار به منظور سازگاری با برنامه‌های قدیمی نگه داشته شده ولی به هر حال Mersenne Twister قابل اطمینان‌تر است. Mersenne Twister نیز به همین ترتیب یکی از PRNGها در SAS است. این روش به طور پیش‌فرض در نرم‌افزار Stata نیز قرار دارد. روش KISS یا (Keep it Simple Stupid) به معنی ساده نگه‌داشتن، به منظور هماهنگی با نسخه‌های قدیمی هنوز در Stata موجود است.

همه مولدهای اعداد تصادفی خانواده KISS سه یا چهار مولد اعداد تصادفی مستقل را با هدف بهبود کیفیت تصادفی ترکیب می‌کنند. مولد اعداد تصادفی KISS در نسخه اصلی که در 1993 معرفی شد، بر اساس ترکیبی از یک «مولد همگام خطی» (linear congruential generator) و دو مولد «ثبات تغییر بازخورد خطی» (Linear-feedback shift register) یا LFSR عمل می‌کرد.

نکته: ساده‌ترین شیوه تولید اعداد تصادفی به صورت مولد همگام خطی یا LCG است که به صورت زیر عمل می‌کند.

$$\large X_{n+1} = (aX_n + b)\; mod(m)$$

مزایا

روش تولید اعداد شبه تصادفی MT، دارای مجوز آزاد (Permissively-licensed) بوده و بدون حق ثبت اختراع برای همه انواع قابل استفاده است. البته نسخه CryptMT این خاصیت را ندارد.
الگوریتم MT، در آزمون‌های بیشمار و متعدد آماری برای نمایش تصادفی بودن را با موفقت پشت‌سر گذاشته است. از جمله آزمون‌ها می‌توان به «تست دایهارد» (Diehard Test) اشاره کرد. البته توجه داشته باشید که MT در همه آزمون‌های TestU01 موفق نبوده است.

نکته: آزمون‌های TestU01 یک کتابخانه نرم افزاری است که به زبان ANSI C پیاده سازی شده و مجموعه‌ای از برنامه‌های کاربردی را برای آزمایش تصادفی بودن مولدهای اعداد تصادفی (RNG) ارائه می‌دهد. این کتابخانه برای اولین بار در سال 2007 توسط «پیر لسیر» (Pierre L’Ecuyer) و «ریچارد سیمارد» (Richard Simard) در دانشگاه مونترال معرفی شد.

در روشی که توسط MT پیاده سازی می‌شود، دوره تناوب یا تکرار اعداد تصادفی بسیار طولانی است به طوری که این دوره تناوب برابر با ۱-2¹⁹⁹³⁷ است. البته توجه داشته باشید که نمی‌توان طولانی بودن این دوره تناوب را تضمینی برای کیفیت اعداد تصادفی تولید شده دانست. اما دوره‌های تناوب کوتاه مدت مانند 2³² که در اکثر بسته‌های نرم افزاری قدیمی استفاده می‌شوند، می‌تواند مشکل ساز شده و کیفیت اعداد تصادفی تولید شده را کاهش دهند.

روش تولید اعداد تصادفی با Mersenne Twister براساس توزیع k و دقت ۳۲ بیتی، دارای خصوصیات خوب و مناسبی برای $$1 \leq k \leq 623$$ است. پیاده سازی‌ها صورت گرفته برای تولید اعداد شبه تصادفی معمولاً اعداد تصادفی را سریعتر از روش‌های تصادفی واقعی (فیزیکی) ایجاد می‌کنند. یک مطالعه نشان می‌دهد که الگوریتم Mersenne Twister اعداد تصادفی ممیز شناور 64 بیتی را تقریباً بیست برابر سریعتر از مجموعه دستورالعمل RDRAND یا (Read Random) مبتنی بر سخت افزار ایجاد می‌کند.

معایب

برای استفاده از روش MT بافر حالت نسبتاً بزرگ است. به طوری که به 2٫5 کیلوبایت حافظه نیاز دارد. البته نسخه دیگری از آن به نام TinyMT که در ادامه مورد اشاره قرار گرفته، میزان استفاده از حافظه را بهینه کرده و با حافظه کمتری قابل استفاده است. همچنین الگوریتم MT، توان متوسط یا ضعیفی براساس استانداردهای مدرن امروزی برخوردار است، مگر اینکه از نوع SFMT استفاده شود. این تکنیک در ادامه متن معرفی شده است.

در مجموعه آزمون TestU01 دو شکست واضح در Crush و BigCrush (دو آزمون پیچیدگی خطی- Linear Complexity) وجود دارد. این آزمون، مانند مرسن توئیستر، بر اساس جبر F2 عمل می‌کند. البته تعدادی مولدهای دیگر برای تولید اعداد شبه تصادفی (PRGN) وجود دارد که از عهده همه آزمایشات بر می‌آیند.

در تولید اعداد تصادفی با Mersenne Twister موارد متعددی وجود دارد که تولید اعداد تصادفی فقط از نظر مقدار دانه (Seed) متفاوت هستند ولی سایر پارامترها با هم تفاوت ندارند به این ترتیب ممکن است مولد MT منجر به تولید اعداد تصادفی یکسانی ‌شود. به طور کلی برای شبیه سازی‌های مونت کارلو که به مولد عدد تصادفی مستقل نیاز دارند، الگوریتم MT مناسب نیست. البته توجه داشته باشید که برای انتخاب مجموعه‌های مختلف مقادیر پارامتر، روش‌‌هایی وجود دارد.

اگر وضعیت اولیه کاملاً تصادفی نباشد، به خصوص اگر حالت اولیه صفرهای زیادی داشته باشد، لازم است برای تولید خروجی که از آزمون‌های تصادفی عبور کند، زمان زیادی صرف کرد. نتیجه این امر آن است که دو نمونه از مولد که با حالت‌های اولیه تقریباً یکسان شروع شده‌اند، برای بسیاری از تکرارها، توالی تقریباً یکسانی را تولید می‌کنند به روزرسانی سال 2002 الگوریتم تولید اعداد تصادفی با Mersenne Twister، مقدار اولیه را بهبود بخشیده است، بنابراین شروع با چنین وضعیتی بسیار بعید است.  گفته می‌شود نسخه مخصوص پردازشگرهای گرافیکی (GPU) که MTGP نامید می‌شود، دارای عملکرد به مراتب بهتری است.

توجه داشته باشید که تولید اعداد تصادفی با Mersenne Twister از نظر رمزنگاری ایمن نیست، مگر اینکه از نوع CryptMT که در ادامه مورد بحث قرار گرفته، استفاده شود. دلیل این امر آن است که مشاهده تعداد تکرار کافی (که در الگوریتم MT19937 برابر با 624 است زیر اندازه بردار حالتی که از آن تکرارهای بعدی تولید می‌شوند را مشخص می‌کند) به شما امکان می‌دهد تمام تکرارهای آینده را پیش بینی کنید.

جایگزین‌هایی برای تولید اعداد تصادفی با Mersenne Twister

همانطور که می‌دانید، روش‌های متعددی برای ایجاد اعداد (شبه) تصادفی وجود دارد. یک مولد جایگزین برای تولید اعداد تصادفی با  Mersenne Twister روش توزیع مناسب با توالی طولانی خطی (Well Equidistributed Long-Period Linear) یا به اختصار WELL است که بازیابی سریع‌تر و تصادفی برابر با MT را ارائه کرده و از سرعت تقریباً یکسانی برخوردار است.

فیلم مجموعه آموزش برنامه نویسی – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

مولد اعداد تصادفی xorshift که توسط «مارسگلیا» (Marsaglia) معرفی شد و نسخه‌های مختلف آن، سریعترین در کلاس «ثبات تبدیل بازخورد خطی» (Linear feedback shift register) یا به اختصار LFSRها هستند.

خانواده ACORN یا عدد «تصادفی همگام جمعی» (Additive Congruential Random Number) که در سال ۱۹۸۹ منتشر شده‌اند، یکی دیگر از روش‌های تولید اعداد شبه تصادفی با توزیع k (توزیع یکنواخت با پارامتر k) هستند که سرعت محاسباتی آن‌ها مشابه MT بوده ولی ویژگی‌های آماری بهتری را نشان می‌دهند، زیرا تمام معیارهای امروزی (2019) TestU01 را برآورده می‌کنند. در صورت استفاده از پارامترهای مناسب، ACORN می‌تواند دوره تناوب دلخواه و دقت بالایی داشته باشد.

توزیع k

یک توالی شبه تصادفی (مثل $$x_i$$ها) از اعداد صحیح w-bit با دوره تناوب P را دارای توزیع $$k$$ با دقت $$v-bit$$ گویند اگر رابطه زیر برقرار باشد.