لأي شيء يصلح هذا المولّد ولأي شيء لا يصلح
تتفاوت المولّدات شبه العشوائية تفاوتًا هائلًا في ما تصلح له. وهذا سريع وقابل للتكرار وحسن السلوك إحصائيًا للاستعمال اليومي، وهو قطعًا ليس مصدرًا للأسرار.
| الاستعمال | صالح؟ | لماذا |
|---|---|---|
| التعليم والمحاكاة وأخذ العيّنات | نعم | قابلية تكرار السحب ميزة هنا |
| اختيار فائز، والنرد، وأرقام اليانصيب | نعم، ببذرة جديدة | من يعرف البذرة يستطيع إعادة السحب |
| كلمات المرور والمفاتيح والرموز ومعرّفات الجلسات | لا | يمكن استرجاع الحالة من المخرجات؛ استعمل مولّد كلمات المرور بدلًا منه |
| الألعاب أو المقامرة الخاضعة للتنظيم | لا | تتطلب مولّدات عتادية معتمدة أو مولّدات تعمية |
- طرفا المجال كلاهما داخله، فالمجال من 1 إلى 100 يحوي 100 قيمة ممكنة.
- وبلا إرجاع لا يمكن أن يتجاوز عدد السحبات عدد القيم في المجال. والحاسبة ترفض بدل أن تكرّر في صمت.
ما هو المولّد شبه العشوائي
مولّد الأعداد شبه العشوائية خوارزمية حتمية تنتج متتالية تجتاز الاختبارات الإحصائية للعشوائية. وهي ليست عشوائية بالمعنى الفيزيائي: فهي علاقة تكرارية ثابتة، ومن قيمة ابتدائية معطاة — البذرة — تنتج المتتالية نفسها دائمًا.
وهذا مولّد xorshift بطول 32 بتًا، نشره جورج مارساغليا في Journal of Statistical Software عام 2003. ويعمل بتطبيق «أو الحصري» مرارًا على قيمة ونسخ مزاحة منها، بثلاثية إزاحة مختارة بحيث تمرّ المتتالية بكل حالة 32 بتية غير صفرية قبل أن تتكرّر.
واستعمال البذرة قرار مقصود لا قيد. فكل حاسبة في هذا الموقع دالة خالصة لمدخلاتها، وهذا ما يجعل النتائج قابلة للتكرار والتحقّق. وهو يمنحك أيضًا ما لا يمنحه مولّد يعمل بالساعة: اذكر البذرة مع أعدادك فيستطيع أي أحد أن يعيد سحبك بالضبط.
كيفية استخدام مولّد الأعداد العشوائية
- حدّد أصغر قيمة وأكبرها. والطرفان كلاهما داخل المجال.
- اختر كم عددًا تسحب.
- قرّر إن كان التكرار مسموحًا. فبلا إرجاع لا يمكن أن تظهر قيمة مرتين، ولذلك لا تستطيع سحب أعداد أكثر مما يحويه المجال.
- غيّر البذرة كلما أردت سحبًا مختلفًا. فالبذرة نفسها تُعيد الأعداد نفسها دائمًا.
كيف تُنتَج الأعداد
تحوّل علاقة xorshift التكرارية حالةً بطول 32 بتًا ثلاث مرات في كل سحبة، ثم تقسمها على 2^32 لتعطي قيمة في المجال من الصفر إلى الواحد دون أن يشمله. وضربها في حجم المجال وأخذ الجزء الصحيح الأدنى يحوّلها إلى عدد صحيح.
أما السحب بلا إرجاع فيستعمل خلطًا جزئيًا بطريقة فيشر-ييتس على المجال. فكل سحبة تُبدّل عنصرًا متبقيًا إلى موضعه، وهو ما يختار مجموعة جزئية عشوائية منتظمة في مرور واحد ولا يمكن أن يتعثّر كما يتعثّر أسلوب «اسحب وأعد المحاولة» كلّما فرغ المخزون.
أخطاء شائعة
- استعمال مولّد شبه عشوائي لأي شيء سرّي. فالمتتالية محدَّدة تمامًا بالبذرة.
- توقّع أعداد جديدة دون تغيير البذرة. فقابلية التكرار هي المقصد، والبذرة هي أداة التحكّم.
- افتراض أن الحدّ الأعلى مستثنى. فطرفا المجال هنا كلاهما داخله.
- طلب قيم مختلفة أكثر مما يحويه المجال.
- قراءة سلسلة من القيم المتشابهة على أنها خلل. فالتجمّع خاصية طبيعية للمتتاليات العشوائية، وغيابه أدعى إلى الريبة من حضوره.
الأسئلة الشائعة
لماذا تعطي البذرة نفسها الأعداد نفسها دائمًا؟
لأن المولّد شبه العشوائي علاقة تكرارية حتمية، والبذرة هي حالتها الابتدائية. وهذه ميزة لا عيب: فذكر البذرة يتيح لأي أحد أن يعيد سحبك بالضبط، وهذا ما يحتاجه البحث القابل للتكرار والعروض الصفّية. ولسحب مختلف غيّر البذرة.
هل هذا عشوائي بما يكفي لسحب جوائز؟
لسحب غير رسمي نعم، شريطة أن تختار بذرة لا يستطيع المشاركون التنبؤ بها وأن تنشرها بعدئذٍ ليمكن التحقّق من النتيجة. أما للألعاب الخاضعة للتنظيم فلا — إذ تتطلب مولّدات عتادية معتمدة أو خوارزميات آمنة تعميًا.
هل أستطيع توليد كلمة مرور بهذا؟
لا. فالحالة الداخلية لمولّد xorshift يمكن استرجاعها من مقطع قصير من مخرجاته، فيصير كل ما يُشتقّ منه قابلًا للتنبؤ. استعمل مولّد كلمات المرور في هذا الموقع بدلًا منه، فهو يسحب من مصدر العشوائية الآمن تعميًا في نظام التشغيل.
ما معنى السحب بلا إرجاع؟
يعني أن أي قيمة لا يمكن أن تظهر أكثر من مرة، كما في سحب كرات اليانصيب. ولمّا كانت كل سحبة تزيل قيمة من المخزون، لا تستطيع سحب أعداد أكثر مما يحويه المجال — فسحب ست قيم مختلفة من مجال فيه خمس أمر مستحيل.
هل الأعداد موزَّعة توزيعًا منتظمًا؟
نعم، إلى حدّ دقة المولّد الأساسي. فكل قيمة في المجال متساوية الاحتمال، ونمط «بلا إرجاع» يستعمل خلطًا جزئيًا بطريقة فيشر-ييتس، وهو يختار كل مجموعة جزئية بحجم معطى باحتمال متساوٍ.
المراجع
- Marsaglia G. Xorshift RNGs. Journal of Statistical Software 2003; 8(14): 1-6. doi:10.18637/jss.v008.i14.
- Knuth DE. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edition. Addison-Wesley, 1997 — random number generation and statistical testing.
- Fisher RA, Yates F. Statistical Tables for Biological, Agricultural and Medical Research. Oliver and Boyd, 1938 — the shuffle used for sampling without replacement.
- L'Ecuyer P, Simard R. TestU01: A C library for empirical testing of random number generators. ACM Transactions on Mathematical Software 2007; 33(4): 22.