🔮 🦕 📶 Algoritma Acak 🖖🏽 🤸🏿 ♿️

Pada artikel ini, Anda akan melihat algoritma ~~sepeda~~ paling beragam untuk menghasilkan angka acak.

Tentang artikel apa

Tentang algoritma menghasilkan nomor pseudorandom yang berbeda dalam kualitas hasil dan kecepatan eksekusi. Artikel ini akan berguna bagi mereka yang ingin mendapatkan generasi nomor kinerja tinggi dalam program mereka atau pengembang perangkat lunak untuk mikrokontroler dan platform lama seperti ZX Spectrum atau MSX.

C ++ rand

Hal pertama yang dipelajari seorang programmer C ++ pemula tentang mendapatkan acak adalah fungsi rand, yang menghasilkan angka acak antara 0 dan RAND_MAX. Konstanta RAND_MAX dijelaskan dalam file stdlib.h dan 32'767, tetapi ini mungkin tidak terjadi, misalnya, di Linux ( lihat komentar ). Jika rand () di kompiler Anda menghasilkan angka dalam 32'767 (0x7FFF) dan Anda ingin mendapatkan angka acak ukuran besar, maka kode di bawah ini dapat dianggap sebagai solusi untuk masalah ini:

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

Implementasi fungsi rand di C lama sederhana dan terlihat seperti ini:

static unsigned long int next = 1;

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

Implementasi ini tidak memiliki distribusi angka yang sangat baik dan sekarang ditingkatkan dalam C ++. Juga, pustaka C ++ standar menawarkan cara-cara tambahan untuk mendapatkan nomor acak, yang dibahas di bawah ini.

C ++ 11 STL acak

Keragaman keacakan ini muncul di C ++ 11 dan terdiri dari serangkaian kelas berikut: minstd_rand, mt19937, ranlux, knuth_b dan berbagai variasi mereka.

Untuk mencegah urutan angka acak dari pengulangan setiap kali program dimulai, "butir" dari generator pseudo-acak diatur dalam bentuk waktu saat ini atau, dalam kasus beberapa permainan retro (dan tidak hanya), interval antara penekanan tombol dari keyboard / joystick. Pustaka acak menyarankan menggunakan std :: random_device untuk mendapatkan biji-bijian yang lebih baik daripada waktu (NULL), namun, dalam kasus kompiler MinGW di Windows, fungsi ini praktis tidak berfungsi sebagaimana mestinya. Masih…

// ,   :
#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(); //

Beberapa algoritma dalam STL acak dapat bekerja lebih cepat daripada rand (), tetapi memberikan urutan angka acak berkualitas rendah.

PRNG - Generator Angka Pseudo-acak

Anda dapat menganggap nama ini sinonim untuk metode kongruen linier. Algoritma PRNG mirip dengan implementasi rand di C dan hanya berbeda dalam konstanta.

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

Algoritma PRNG cepat dan mudah diimplementasikan dalam banyak bahasa, tetapi tidak memiliki periode besar.

Xorshift

Algoritma memiliki banyak variasi, berbeda satu sama lain berdasarkan periode dan register yang digunakan. Detail dan varietas XorShift dapat dilihat di Wikipedia atau Habré. Saya akan memberikan salah satu opsi dengan urutan 2 di tingkat 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;
}

Generator ini sangat bagus karena tidak ada operasi pembagian dan perkalian sama sekali - ini dapat berguna pada prosesor dan mikrokontroler di mana tidak ada instruksi assembler divisi / perkalian (PIC16, Z80, 6502).

8-bit acak dalam emulator z26

Z26 adalah emulator dari awalan Atari2600 lama, dalam kode yang Anda dapat menemukan berorientasi secara acak untuk bekerja dengan register 1-byte.

// 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;
}

Pernah saya harus membuat implementasi algoritma ini untuk z80:

Kode perakitan

;    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

Acak ringkas untuk Z80 dari Joe Wingbermuehle

Jika Anda tertarik untuk menulis program untuk mobil dengan zilog, maka saya persembahkan kepada Anda sebuah algoritma dari Joe Wingbermuehle (hanya bekerja pada 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

Random House Generator di DOOM

Dalam kode sumber permainan Doom terdapat file yang menarik bernama m_random.c (lihat kode) , yang menjelaskan fungsi keacakan "tabel", yaitu, tidak ada formula dan sihir dengan sedikit pergeseran sama sekali.

Saya akan memberikan kode yang lebih ringkas yang dengan jelas menunjukkan operasi fungsi ini.

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];
}

Varik untuk 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

Tentu saja, ini bukan acak dan urutan angka acak mudah diprediksi bahkan pada tingkat intuisi selama pertandingan, tetapi semuanya bekerja sangat cepat. Jika kekuatan kriptografi tidak terlalu penting bagi Anda dan Anda menginginkan sesuatu yang dengan cepat menghasilkan "tipe-acak", maka fungsi ini adalah untuk Anda. By the way, di Quake3, acak terlihat sederhana - rand () & 0x7FFF.

RDRAND

Beberapa prosesor modern mampu menghasilkan angka acak dengan instruksi assembler tunggal - RDRAND. Untuk menggunakan fungsi ini dalam C ++, Anda dapat secara manual menulis instruksi yang diperlukan dengan menyisipkan assembler atau menghubungkan file immintrin.h di GCC dan memilih salah satu variasi fungsi _rdrandXX_step, di mana XX berarti jumlah bit dalam register dan mungkin 16, 32 atau 64.

#include <immintrin.h>

unsigned val;
_rdrand32_step(&val);

Jika Anda melihat kesalahan kompilasi, itu berarti Anda tidak mengaktifkan flag -mrd atau compiler / prosesor Anda tidak mendukung alat ini. Ini mungkin merupakan penghasil bilangan acak tercepat, tetapi ada pertanyaan tentang kekuatan kriptografiknya, jadi pikirkanlah.

Akhir

Kelas std :: minstd_rand dari pustaka acak STL lebih cepat daripada rand () biasa dan dapat menjadi pengganti alternatif jika Anda tidak terlalu khawatir tentang lamanya periode dalam minstd. Mungkin ada perbedaan dalam cara fungsi-fungsi ini bekerja pada Windows dan Unix.

INFA pada topik

Artikel tentang C ++ 11 acak dan beberapa fitur yang bisa digunakan dengannya: Pembuatan Angka Acak di C ++ Modern
Apa saja generator di STL acak? pengasingan
Artikel wiki tentang XorShift dengan implementasi berbeda: tyk
Git emulator z26. Kode acak dalam file c_pitfall2.c: git
Dumchik generator acak: git

PS Artikel pertama saya. Tulis apa yang berlebihan, apa yang harus ditambahkan / dikurangi

Algoritma Acak