🚁 🤾🏿 🙅 خوارزميات عشوائية 🤦🏻 👩🏻‍🎨 🏼

في هذه المقالة ، سترى خوارزميات ~~الدراجات~~ الأكثر تنوعًا لإنشاء أرقام عشوائية.

حول أي مقال

حول الخوارزميات إنشاء أرقام عشوائية زائفة تختلف في جودة النتيجة وسرعة التنفيذ. ستكون المقالة مفيدة لأولئك الذين يرغبون في الحصول على عدد عالي الأداء من الجيل في برامجهم أو مطوري البرامج للتحكم الدقيق والمنصات القديمة مثل ZX Spectrum أو MSX.

C ++ راند

أول شيء يتعلمه مبرمج C ++ المبتدئ حول الحصول على منزل عشوائي هو وظيفة الراند ، التي تولد رقمًا عشوائيًا بين 0 و RAND_MAX. يتم وصف ثابت RAND_MAX في ملف stdlib.h وهو 32'767 ، ولكن قد لا يكون هذا هو الحال ، على سبيل المثال ، في Linux ( انظر التعليق ). إذا كان rand () في المترجم الخاص بك يولد أرقامًا ضمن 32'767 (0x7FFF) وتريد الحصول على عدد عشوائي من الحجم الكبير ، فيمكن اعتبار الرمز أدناه كحل لهذه المشكلة:

int64_t A = rand();
A <<= 15; //   15,   7FFF  15 
A |= rand();
A <<= 15;
A |= rand();
A <<= 15;
A |= rand();
A <<= 3;
A |= rand() & 0b111; //  3

كان تنفيذ وظيفة الراند في لغة C القديمة بسيطًا وشبهه:

static unsigned long int next = 1;

int rand()
{
  next = next * 1103515245 + 12345;
  return (unsigned int)(next / 65536) % 32768;
}

لم يكن لهذا التطبيق توزيع جيد جدًا للأرقام وقد تم تحسينه الآن في C ++. أيضًا ، توفر مكتبة C ++ القياسية طرقًا إضافية للحصول على رقم عشوائي ، والتي سيتم مناقشتها أدناه.

C ++ 11 STL عشوائي

ظهر هذا التنوع العشوائي في C ++ 11 ويتكون من مجموعة الفئات التالية: minstd_rand و mt19937 و ranlux و knuth_b وتنويعاتها المختلفة.

لمنع تسلسل الأرقام العشوائية من التكرار في كل مرة يتم فيها تشغيل البرنامج ، يتم تحديد "حبة" المولد العشوائي الزائف في شكل الوقت الحالي أو ، في حالة بعض الألعاب القديمة (وليس فقط) ، الفترات الفاصلة بين ضغطات المفاتيح من لوحة المفاتيح / عصا التحكم. تقترح المكتبة العشوائية استخدام std :: random_device للحصول على الحبوب بشكل أفضل من الوقت (NULL) ، ومع ذلك ، في حالة مترجم MinGW على Windows ، لا تعمل الوظيفة عمليًا كما ينبغي. ما يزال…

// ,   :
#include <random>
#include <ctime>

std::mt19937 engine; // mt19937    
engine.seed(std::time(nullptr));
/*
 ,    UNIX--    MinGW
std::random_device device;
engine.seed(device());
*/
int val = engine(); //

قد تعمل بعض الخوارزميات في STL عشوائيًا بشكل أسرع من rand () ، ولكنها تعطي تسلسلًا أقل جودة للأرقام العشوائية.

PRNG - مولد الأرقام العشوائية الزائفة

يمكنك اعتبار هذا الاسم مرادفًا لطريقة التطابق الخطي. خوارزميات PRNG تشبه تطبيق الراند في C وتختلف فقط في الثوابت.

unsigned PRNG()
{
  static unsigned seed = 1; //     0
  seed = (seed * 73129 + 95121) % 100000;
  return seed;
}

خوارزميات PRNG سريعة وسهلة التنفيذ في العديد من اللغات ، ولكن ليس لديها فترة كبيرة.

Xorshift

تحتوي الخوارزمية على العديد من الاختلافات ، تختلف عن بعضها البعض حسب الفترة والسجلات المستخدمة. يمكن الاطلاع على تفاصيل وأنواع XorShift على ويكيبيديا أو حبري. سأعطي أحد الخيارات بتسلسل 2 في الدرجة 128.

struct seed_t
{
  unsigned x = 1; //     
  unsigned y = 123;
  unsigned z = 456;
  unsigned w = 768;
};

unsigned XorShift128()
{
  static seed_t s;
  unsigned t = s.x^(s.x<<11);
  s.x = s.y;
  s.y = s.z;
  s.z = s.w;
  s.w = (s.w^(s.w>>19)) ^ (t^(t>>8));
  return s.w;
}

هذا المولد جيد جدًا لأنه لا يحتوي على عمليات تقسيم وضرب على الإطلاق - يمكن أن يكون هذا مفيدًا في المعالجات ووحدات التحكم الدقيقة التي لا توجد بها تعليمات قسم / الضرب المجمعة (PIC16 ، Z80 ، 6502).

8 بت عشوائي في محاكي z26

Z26 هو محاكي لبادئة Atari2600 قديمة ، في الكود يمكنك العثور على رمز عشوائي موجّه للعمل مع سجلات 1 بايت.

// P2_sreg - static uint8_t
void P2_Read_Random()
{
  P2_sreg =
    (((((P2_sreg & 0x80) >> 7) ^
       ((P2_sreg & 0x20) >> 5)) ^
      (((P2_sreg & 0x10) >> 4) ^
       ((P2_sreg & 0x08) >> 3))) ^ 1) |
        (P2_sreg << 1);
  DataBus = P2_sreg;
}

بمجرد أن اضطررت إلى تنفيذ هذه الخوارزمية لـ z80:

رمز التجميع

;    z26
; a - output
; rdseed - 1  
randz26:
    exx

    ld a,(rdseed)
    and 20h
    sra a
    sra a
    sra a
    sra a
    sra a
    ld h, a

    ld a,(rdseed)
    and 80h
    sra a
    sra a
    sra a
    sra a
    sra a
    sra a
    sra a
    xor h
    ld l, h
    
    ld a,(rdseed)
    and 08h
    sra a
    sra a
    sra a
    ld h, a

    ld a,(rdseed)
    and 10h
    sra a
    sra a
    sra a
    sra a
    xor h
    ld h, a
    ld a, l
    xor h
    xor 1

    ld h, a
    ld a,(rdseed)
    sla a
    or h
    ld (rdseed),a

    exx
    ret

المدمجة العشوائية ل Z80 من جو Wingbermuehle

إذا كنت مهتمًا بكتابة برامج للسيارات مع zilog ، فأقدم انتباهكم إلى خوارزمية من Joe Wingbermuehle (تعمل فقط على zilog):

; By Joe Wingbermuehle
; a res 1 byte - out val
; rdseed res 1 byte - need for rand. != 0
rand8:
        exx
        ld      hl,(rdseed)
        ld      a,r
        ld      d,a
        ld      e,(hl)
        add     hl,de
        add     a,l
        xor     h
        ld      (rdseed),hl
        exx
        ret

مولدات عشوائية في DOOM

في الكود المصدري للعبة Doom ، يوجد ملف مثير للاهتمام يسمى m_random.c (انظر الكود) ، والذي يصف وظيفة عشوائية "الطاولة" ، أي أنه لا توجد صيغ وسحر مع تحولات بت على الإطلاق.

سأعطيك رمزًا أكثر إحكاما يوضح بوضوح تشغيل هذه الوظيفة.

const uint8_t random_map[] =
{
  4,  1,   63, 3,
  64, 22,  54, 2,
  0,  52,  75, 34,
  89, 100, 23, 84
};

uint8_t get_random()
{
  static uint8_t index = 0;
  index = (index + 1) & 0xF; // 0xF,      random_map
  return random_map[index];
}

فاريك ل z80

;   (  DOOM)
; rand_table -    .  
;                        256    .
; a - output num
randtab:
    exx
    ; index
    ld a, (rdseed)
    inc a
    ;and filter ; for crop array index
    ld (rdseed), a
    ; calc array address
    ld hl, rand_table
    ld d, 0
    ld e, a
    add hl, de
    ld a, (hl) ; get num from arr
    exx
    ret

بالطبع ، هذا ليس عشوائيًا ومن السهل التنبؤ بتسلسل الأرقام العشوائية حتى على مستوى الحدس أثناء اللعبة ، ولكن كل ذلك يعمل بسرعة كبيرة. إذا لم تكن قوة التشفير مهمة بالنسبة لك وتريد شيئًا يولد بسرعة "نوع عشوائي" ، فإن هذه الوظيفة مناسبة لك. بالمناسبة ، في Quake3 ، تبدو عشوائية بسيطة - rand () & 0x7FFF.

RDRAND

بعض المعالجات الحديثة قادرة على توليد أرقام عشوائية بإرشاد مجمع واحد - RDRAND. لاستخدام هذه الوظيفة في C ++ ، يمكنك كتابة التعليمات اللازمة يدويًا باستخدام إدخالات التجميع ، أو توصيل ملف immintrin.h في GCC وتحديد أي من اختلافات دالة _rdrandXX_step ، حيث تعني XX عدد البتات في التسجيل ويمكن أن تكون 16 أو 32 أو 64.

#include <immintrin.h>

unsigned val;
_rdrand32_step(&val);

إذا رأيت خطأ تجميع ، فهذا يعني أنك لم تقم بتمكين علامة -mrdrnd أو أن المترجم / المعالج الخاص بك لا يدعم هذه الأداة. قد يكون أسرع مولد للأرقام العشوائية ، ولكن هناك أسئلة حول قوة التشفير ، لذا فكر في الأمر.

تنتهي

تعمل فئة std :: minstd_rand من مكتبة STL العشوائية بشكل أسرع من الراند العادي () ويمكن أن تصبح بديلاً بديلًا إذا لم تكن مهتمًا بشكل خاص بطول الفترة في minstd. قد تكون هناك اختلافات في كيفية عمل هذه الوظائف على Windows و Unix.

INFA على الموضوع

مقال عن C ++ 11 عشوائي وبعض ميزات العمل معه: Random Number Generation in Modern C ++
ما هي المولدات في STL عشوائي؟ منفى
مقالة ويكي عن XorShift مع تطبيقات مختلفة: tyk
محاكي Git z26. كود عشوائي في ملف c_pitfall2.c: git
Dumchik مولد عشوائي: بوابة

PS مقالتي الأولى. اكتب ما هو غير ضروري وما يجب إضافته / تقليله

خوارزميات عشوائية