AVR, آردوینو arduino, آموزش, توصیه شده, مقاله

چگونه اعداد تصادفی واقعا تصادفی بسازیم!

ساخت اعداد تصادفی

شاید برای شما هم پیش آمده باشد که برای ساخت یک بازی یا الگوریتم رمزگذاری یا هر منظور دیگری نیاز به ساخت اعداد تصادفی داشته باشید! ممکن است فکر کنید که ساخت یک عدد تصادفی کار زیاد پیچیده‌ای نیست و با صدازدن یک تابع Rand یا تابعی مشابه آن، کار تمام می‌شود. اما عدد تولیدشده با این روش چقدر تصادفی است؟ آیا نتیجه قابل تکرار نیست؟

در این مقاله قصد داریم این موضوع را مورد کنکاش قرار دهیم. پس با سیسوگ همراه شوید.

چرا نمی توان اعداد تصادفی را واقعا تصادفی نامید؟

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

برای روشن‌تر شدن مسئله فوق به مثال زیر توجه کنید:

در برنامه فوق ما قصد داشتیم که 10 عدد تصادفی ایجاد کنیم و نتیجه را نمایش دهیم. برای این کار از یک حلقه استفاده می‌کنیم که 10 بار تابع rand را فراخوانی کند و نتیجه را نمایش دهد. به نظر توالی اعداد تولیدشده اتفاقی هستند.

البته در نظر داشته باشید این توالی تا وقتی اتفاقی است که ما از الگوریتم تولید آنها اطلاع نداشته باشیم. وقتی الگوریتم را مطالعه کنیم و روش عملکرد آن را دربیابیم با داشتن یکی از اعداد می‌توانیم عدد بعدی و حتی قبلی را حدس بزنیم! در این مرحله این مسئله را نادیده می‌گیریم.

انتظار داریم که با هر بار اجرای برنامه ده عدد کاملاً اتفاقی داشته باشیم؛ اما هر بار که برنامه را اجرا می‌کنیم، همین ده عدد نمایش داده می‌شوند. (ممکن است برای شما ده عدد دیگر باشد ولی نتیجه تکرارپذیر است.) یعنی اعداد واقعاً تصادفی نیستند و توسط الگوریتمی ایجاده شده‌اند که هیچ پارامتر متغیری نداشته است.

برای رفع این نقص، تابعی وجود دارد به نام srand که با دریافت یک عدد، اعداد تصادفی را از آن نقطه شروع خواهد کرد. به این معنی که اگر در هر بار اجرای برنامه، ما یک عدد تصادفی (که خود ساخت این عدد نیز مسئله‌ساز است.) به این تابع بدهیم، خروجی نیز اعداد تصادفی است!

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

 

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

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

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

چرا در سیستم‌های میکروکنترلری وضع حاد‌تر است؟

معمولاً در سیستم‌های مبتنی بر میکروکنترلر، زمان واقعی (RTC) وجود ندارد و زمان سیستم معمولاً از زمان روشن شدن دستگاه سنجیده می‌شود. خود این مسئله باعث می‌شود که عملاً تابع srand بی‌استفاده شود؛ چراکه مثلاً همیشه در زمان خاصی از اجرای برنامه فراخوانی می‌شود و همیشه یک مقدار خاص به آن داده می‌شود. برای روشن شدن مسئله، برنامه بالا را برای سخت‌افزار آردوینو بازنویسی می‌کنیم.

 

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

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

 

راه‌حل تولید اعداد تصادفی واقعی چیست؟

ااما راه‌حل اساسی برای تولید اعداد واقعاً تصادفی چیست؟

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

روش‌های متفاوتی برای تولید اعداد تصادفی با استفاده از اصول ذکرشده وجود دارد. اما روش‌هایی که چندان پیچیده نباشند و بتوان به‌راحتی آن‌ها را پیاده‌سازی کرد محدود هستند. ما در این مقاله قصد داریم تا برای تولید اعداد تصادفی از نویز سفید (White Noise) استفاده کنیم. از نظر فیزیکدانان نویز سفید سیگنالی تصادفی است که تراکم طیفی ثابتی دارد.
اگر بخواهیم به شکل ساده‌تر مسئله را بیان کنیم باید بگوییم که مثلاً گوش ما انسان‌ها، معمولاً محدوده‌ی فرکانس ۲۰ هرتز تا ۲۰ هزار هرتز را می‌شنود. اگر یک دستگاه صوتی بخواهد نویز سفید برای گوش ما تولید کند، باید توان امواجی که از آن در محدوده فرکانسی ۲۰ تا ۴۰ هرتز ساطع می‌شود، با توان امواجی که مثلاً در محدوده فرکانسی ۱۰۰۰۰ و ۱۰۰۲۰ ساطع می‌شود، برابر باشد.

 

صدای نویز سفید را بشنوید:

صدای اقیانوس نیز نویز سفید است:

 

چگونه نویز سفید بسازیم؟

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

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

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

مدار نهایی به شکل زیر خواهد بود:

چگونه می‌توانم از ژنراتور نویز سفید استفاده کنم؟

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

در برنامه زیر برای ایجاد یک عدد تصادفی از نویز سفید و ADC به کمک توابع Rand و Srand استفاده شده است.

بررسی نتایج

خروجیِ دیجیتالِ مدارِ رندم ژنراتور را برای مدت 15 ساعت با نرخ نمونه‌برداری 500 میکروثانیه ذخیره و موردبررسی قراردادیم که نتایج زیر به‌دست آمد:

اگر هر بیت را یک پیکسل فرض کنیم و داده‌های ذخیره‌شده را به‌صورت یک عکس آشکار کنیم، تصویر زیر به‌دست خواهد آمد که شباهت زیادی به تصویر برفکی تلویزیون‌ها دارد.

نمودار پراکندگی داده‌های موجود:

882000 نمونه اول را به صورت فایل صوتی بشنوید:

نوشته های مشابه

14 دیدگاه در “چگونه اعداد تصادفی واقعا تصادفی بسازیم!

  1. Sajjad Azadfalah سجاد گفت:

    سلام سپاسگزارم عالی بود
    یک سوال من متوجه شدم میکرو کنترلر های STM32 یک قابلیت برای ایجاد اعداد تصادفی واقعی دارند شما راجب اون اطلاعی دارید ؟
    سپاس

    1. زئوس Zeus زئوس Zeus گفت:

      سلام خواهش میکنم دوست عزیز
      بله درست متوجه شدید ، توی سری F4 به بعد واحد RNG یا Random Number Generator اضافه شده که دقیقا چنین کاری رو انجام میده !
      کار کردن باهاش خیلی ساده است اگر شد انشالله بررسیش خواهیم کرد.

  2. امید گفت:

    یک پیشنهاد اینه که به جای استفاده امدار پیچیده نویز سفید از یک سنسور دما استفاده کرد یا برخی میکرو کنترلر ها خودشون دارای سنسور دما هستند و یا میشه یک سنسور دمای ساده رو بدون هیچ فیلتر و خازن بر روی تغذیش استفاده کرد با کمی تغییر در مغدار adc میشه اعداد رندم ساخت

    1. زئوس Zeus زئوس Zeus گفت:

      پیشنهاد خوبیه ! و اغلب مواقع فابل استفاده و البته هوشمندانه است ، ولی همیشه بیم این میره که تو شرایط دمایی یکسان نتایج تکرار شوند !
      فکر میکنم اگر فلسفه مساله رو مد نظر قرار بدیم ، یعنی حتی نتونیم شرایطی ایجاد کنیم که نتایج تکرار شوند. ول

  3. مرتضی گفت:

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

    1. زئوس Zeus زئوس Zeus گفت:

      بله کاملا درسته ؛ به عنوان نمونه خانواده STM32F4 به بعد داری چنین قابلیتی هستند.

  4. مهرداد گفت:

    سلام
    من برای ساختن یک تاس الکترونیکی از میکروکنترلر استفاده کردم
    برای تولید اعداد 1 تا 6 ساده ترین راه را انتخاب کردم
    بین یک DO LOOP هر بار نتغیر را مساوی با یکی از این اعداد قرار دادم و برای غیرقابل حدس زدن کردنش . ترتیب چیدمان اعداد را بهم ریختم . وبعلاوه هر کدام را بصورت تصادفی دوبار تکرار کردم مثلا اینطوری n=1 n=6 n=3 n=5 n=6 n=3 n=2 n=4 n=1
    بین هر یک هم یک وقفه گذاشتم . و دستورif switch=1 then goto show
    به نظر خودم این تاس خیلی خوب و اعداد تصادفی تولید میکنه .
    نظر شما چیه؟

    1. زئوس Zeus زئوس Zeus گفت:

      سلام دوست عزیز روش جالبی به کار بردید ولی تا برنامه رو نبینم نمیشه گفت که واقعا اینطور هست یا خیر 🙂

    2. امید گفت:

      به نظرم از زمان فشردن سوئیچ که توسط یک عامل خارجی مثل انسان ایجاد میشه برای غیر قابل پیش بینی شدنش استفاده کردید درسته ؟

      1. زئوس Zeus زئوس Zeus گفت:

        بله کاملا درسته ؛ استفاده از عومل خارجی تاثیر زیادی در غیر قابل پیش بینی شدن خواهند داشت.

  5. Alaa گفت:

    باسلام و تشکر از توضیحات عالی اقای زئوس

    در یک برنامه یک بازی شانس وجود داره باعنوان صفر تا 36 و البته عدد زوج و فرد …
    بدین ترتیب ک ابتدا کاربر یک عدد مثلا 3رو انتخاب میکنه بعد برنامه عدد تصادفی رو میگه اگ همون 3بود ک برد اعلام میکنه و امتیاز میده اگ نه ک هیچ….
    حالا میخاستم بدونم ک راهی برای حدس اعداد تصادفی ک تولید میکنه وجود داره؟چطور میشه الگوریتم رو تشخیص داد باتشکر..
    باتوجه به مقاله ظاهرا هیچ وقت نمیشه عدد تصادفی واقعی تولید کرد فقط حدس زدن ورودی رو مشکل تر میشه کرد

    1. زئوس Zeus زئوس Zeus گفت:

      سلام دوست عزیز ، قطعا غیر ممکن وجود ندارد ، ولی پیدا کردن الگوی بکار رفته اصلا کار ساده ای !
      با فرض این که دستگاه موصوف از موتور تولید اعداد تصافی استفاده نکرده باشد (آنچه در این مقاله توضیح داده شد) ، با چند روش میتوان الگوریتم را پیدا کرد ؛ البته کار ساده ای نیست ، شما حداقل نیاز دارید که بدونید دستگاه چه مدته که روشنه و داره کار میکنه و البته این که تا حالا چند عدد تصادفی ایجاد کرده ، بعد از اون میتونید حدس بزنید که الگوریتم چی هست اونم با استفاده از سلسله اعدادی که تولید میکنه :/
      و اما راه ساده تر وقتی دستگاه روشن شده و هیچ اعداد تصافیی تولید نکرده ، شما 5 بار بازی کنید ، و اعداد تولیدی رو نگاه کنید ، مثلا 1و7و15و28و33 ، دستگاه رو خاموش کنید روشن کنید باز 5 بار بازی کنید اگر همون اعداد رو تولید کرد که خوب معلوم میشه از موتور تولید اعداد تصافی استفاده نمیکنه و میتونید سلسله اعدادی که تولید میکنه رو یاداشت کنید و برای دفعه بعد ارشون استفاده کنید 🙂

  6. سیما درزی علی گفت:

    عالی بود. من قبلا به این مشکل برخورده بودم. جالب اینجا بود که نتیجه تابع RND در بسکام ، توی شبیه سازی پروتئوس با نتیجه عملی یکسان بود.

    من دقیقا یک حلقه For با 10 بار تکرار درست کرده بودم و انتظار داشتم با هر بار بالا اومدن میکرو یک سری اعداد متفاوت تحویل بگیرم. اما اعداد همیشه تکراری بودن.

    1. زئوس Zeus زئوس Zeus گفت:

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

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *