تولید اعداد تصادفی

توجه: این صفحه صرفا به صورت عمومی درباره ی اگوریتم های شبیه ساز تولید اعداد تصادفی یا pseudorandom number generator algorithms می باشد. اگر نیاز به دانستنی های مرتبط با این موضوع در علوم کامپیوتری دارید، لطفا به این صفحه مراجعه فرمایید : Pseudorandom generator . البته خواندن این صفحه هم میتونه دیدگاه شما رو بهبود ببخشد.

Two red dice 01.svg

یک random number generator (RNG) دستگاه یا تابع یا تولید کننده یی هست که یک سری اعداد دنباله هم رو به صورت رندم تولید می کند.

اعداد رندم چیست؟ در ساده ترین مثال ممکن مثلا با استفاده از تاس یک عدد ده رقمی که تک تک رقم ها با پرتاب تاس جمع آوری شده است، تولید می شود. این یک عدد رندم هست. مثلا 2561421121.

این یک عدد تصادفی تولید شده با یک وسیله ی فیزیکی بود. میتونست سکه یا هر چیز دیگری که بتونه عدد رو نمایش بده و با پرتابش یه عدد رندم نشون بده.

این روش hardware random-number generators (HRNG) نام دارد. اعداد تولید شده در این روش واقعا تصادفی هستن و به هیچ روش منطقی نمیتونیم این عدد ده رقمی رو پیش بینی کنیم و کاملا شانسی هست.

اما در کامپیوتر چی؟ که همه چیز عدد و منطق و صفر و یک هست. تابع هایی که عدد رندم تولید میکنند واقعا تاس یا سکه پرتاب نمیکنند. این تابع ها یک شبیه ساز تولید اعداد رندم هست. به این مدل ها هم pseudo-random number generators (PRNG) گفته میشود. این تولید کننده ها الگوی مشخصی دارند و با استفاده از ترکیب مواردی مختلف اعداد رندم را تولید و در کنار همدیگر قرار می دهند.

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

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


متد ها و روش های زیادی برای بدست آوردن دنباله ی اعداد تصادفی وجود دارد. هر چند در مورد این PRNG ها بررسی و تست ها و نتیجه های زیادی هست تا نشان دهند این اعداد غیر قابل پیش بینی هستند ولی با این حال از این متد ها در مباحث کریپتوکارنسی استفاده نمیشود. برای این منظور cryptographically secure pseudo-random number generators (CSPRNG) تولید شده اند که در تولید اعداد تصادفی که به عنوان کلید خصوصی در این مباحث شناخته می شود، استفاده می شوند.


روش‌های فیزیکیویرایش

برخی از پدیده‌های طبیعی الگوهای مناسبی برای تولید این اعداد هستند به عنوان مثال برخی پدیده‌های فیزیکی از جمله اختلالات حرارتی در دیودهای زنر (Zener Diodes) دارای رفتاری کاملاً تصادفی هستند و می‌توانند پایه‌ای برای تولید RNGهای فیزیکی و سخت‌افزاری باشند.

همانطور که اشاره شد، الگوهای طبیعی جالبی برای تولید اعداد تصادفی وجود دارد؛ یک روش متداول استفاده از یک تابع درهم ساز (که ورودی اش جریانی از فریم‌های ویدئوییٍ یک منبع غیرقابل پیش‌بینی می‌باشد) است. به عنوان مثال لاواراند (Lavarand)از تصاویر تعدادی لامپ لاوا(Lava Lamps) استفاده کرد. Lithium Technologies از تصاویر آسمان و Random.org از صداهای آشفته جوی استفاده می‌کند.

روش‌های محاسبه‌ایویرایش

تولیدکننده‌های اعداد شبه تصادفی الگوریتم‌هایی با قابلیت تولید اعداد تصادفی هستند هرچند اعداد تولید شده توسط آن‌ها به‌طور تناوبی تکرار می‌شود یا آنکه حافظه زیادی را اشغال می‌کنند. یکی از متداولترین تولیدکننده‌های اعداد تصادفی، LCG Linear Congruential Generator است که رابطه‌ای بازگشتی دارد:

 

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

یک روش ساده که با قلم و کاغذ نیز قابل اجراست روش میانه مربع (Middle Square Method) است که توسط جان فون نیومن (John Von Neumann) ابداع شد که بسیار ساده‌است ولی اعداد تولیدی آن از لحاظ آماری کیفیت خوبی ندارند.

بسیاری از زبان‌های برنامه‌نویسی رایانه شامل توابع کتابخانه‌ای هستند که برای تولید اعداد تصادفی (یک بایت، کلمه ویا اعداداعشاری تصادفی با توزیع یکنواخت بین ۰ و ۱)طراحی شده‌اند. این توابع کتابخانه‌ای اغلب از لحاظ خصوصیات آماری ضعیف هستند و الگوهایشان پس از تنها ۱۰۰۰ رشته دوباره تکرار می‌شود، آن‌ها اغلب با زمان واقعی رایانه به عنوان seed راه‌اندازی می‌شوند. در واقع این توابع در بعضی موارد به تعداد کافی رویداد تصادفی تولید می‌کنند (مثلاً در بازی‌های ویدئویی) ولی وقتی رویدادهای تصادفی با کیفیت بالا مورد نظر است، ناکارآمد هستند (مثلاً در رمزنگاری).

کاربردهای اعداد تصادفیویرایش

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

کتاب‌های بسیاری نیز در همین مورد نوشته شده‌اند.

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

تولید اعداد تصادفی در رایانهویرایش

از آن‌جایی‌که رایانه‌ها ماشین‌هایی از نوع معیّن (Deterministic) هستند، با دریافت ورودی یکسان، همیشه یک خروجی بیرون می‌دهند. ازین رو تولید اعداد تصادفی در رایانه مبحثی است که در این مقاله به بررسی آن می‌پردازیم.

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

هر بار که این تابع صدا زده می‌شود، رایانه عدد تولید شدهٔ پیشین را به عنوان ورودی جدید تابع تولید عدد تصادفی می‌فرستد. منشاء مشکل نیز در همین مرحله است.

هر بار که این تابع صدا زده شود، بر اساس ماهیت جبری ماشین و با توجه به مقدار اولیهٔ فرستاده شده به تابع تولید عدد تصادفی (seed) باید با یک دنباله از اعداد مشابه یکدیگر مواجه شویم.

مثال در دنیای واقعیویرایش

در زبان برنامه‌نویسی جاوا، کلاسی وجود دارد با نام Random که دو نوع Constructor دارد. نوع اول آن ورودی دریافت نمی‌کند ولی نوع دوم آن یک عدد long به عنوان seed که همان ورودی اولیهٔ تابع تولید عدد تصادفی است، دریافت می‌کند.

یک شیٔ از این کلاس برای تولید دنباله‌ای از اعداد شبهتصادفی به کار می‌رود. این کلاس از جاوا دارای متدهایی مانند next که برای دریافت عدد شبه تصادفی بعدی است، است. اگر seed یا مقدار اولیهٔ فرستاده شده به Constructor یکسان باشد. ما با گرفتن اعداد بعدی از دو شیٔ با دنباله‌ای کاملاً یکسان از اعداد مواجه می‌شویم. در زیر قسمتی از تابع next در کلاس Random را مشاهده می‌کنید.

 synchronized protected int next(int bits) {
       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L <<48) - 1);
       return (int)(seed>>> (48 - bits));
 }

این تابع و در واقع روش پیش‌روی و به دست آوردن seed یا مقدار اولیهٔ بعدی در جاوا، برگرفته از روش پیشنهادی دونالد کنوت در کتاب هنر برنامه‌نویسی رایانه می‌باشد.

چگونه مقدار اولیه مناسب را پیدا کنیم؟ویرایش

در برنامه‌نویسی به عنوان مثال برای نوشتن یک بازی راه‌حل‌های گوناگونی مانند قرار دادن مقدار اولیه برابر با تعداد بازی‌های انجام شده بر روی رایانه یا ذخیرهٔ خروجی آخرین seed از برنامهٔ قبلی در حال اجرا است. با اینحال کماکان مشکل مقدار دهی اولین seed پابرجاست.

اولین مقدار اولیهویرایش

راحت‌ترین راه حل این مسئله در دنیای کامپیوتر استفاده از زمان فعلی دستگاه است. کامپیوترهای امروزی زمان را با دقت میلی‌ثانیه در دسترس دارند. برنامه‌ها می‌توانند زمان اولین اجرای خود را به عنوان seed به اولین باری که تابع تولید اعداد تصادفی صدا زده می‌شود، بفرستند. ولی اگر باز هم دونفر به‌طور کاملاً هم‌زمان برنامه را اجرا کنند خروجی یکسان دریافت خواهند کرد. این مشکل هم با افزودن معیارهای دیگری به seed مانند زمان آخرین کلیک ماوس (Mouse Click)، مدت زمان بالا بودن سیستم‌عامل و مواردی مشابه، به مقدار زیادی کاهش داد. با افزودن این معیارها و معیارهای مشابه دیگر به برنامه احتمال ایجاد تشابه را به سمت صفر کاهش می‌دهیم.

در همان زبان برنامه‌نویسی جاوا که به عنوان نمونه آورده شد، ورودی Constructor یک عدد از نوع اولیهٔ long به عنوان ورودی می‌گیرد. این عدد long یک عدد ۶۴ بیتی در جاوا است که خود باعث محدود شدن seed و امکان به وجود آمدن اعداد تصادفی برابر را فراهم می‌سازد. بنابر این مشکل کاملاً حل نشده‌است.

اعداد شبه تصادفیویرایش

همانطور که دیدیم اعداد تصادفی تولید شده توسط رایانه و محاسبات ریاضی اعداد کاملاً تصادفی نبوده و از اینرو این اعداد را اعداد شبه تصادفی می‌نامند.

روش‌های فیزیکی و سخت‌افزاری تولید اعداد تصادفیویرایش

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

  1. استفاده از صداهای جوی دریافت شده توسط رادیوی متصل به رایانه.
  2. تابش حاصل از شکافت هسته‌ای که توسط یک Geiger counter متصل به رایانه دریافت می‌شود.

جستارهای وابستهویرایش

منابعویرایش

بخش رایانه:

پانویسویرایش

پیوند به بیرونویرایش