Алгоритмы рандома

Про что статья

Про алгоритмы генерирующие псевдослучайные числа, которые отличаются между собой качеством результата и скоростью исполнения. Статья будет полезна тем, кто хочет получить высокопроизводительную генерацию чисел в своих программах или разработчикам софта для микроконтроллеров и старых платформ по типу ZX Spectrum или MSX.

C++ rand

Первое что узнаёт начинающий программист С++ по теме получения рандома — функция rand, которая генерирует случайное число в пределах от 0 и RAND_MAX. Константа RAND_MAX описана в файле stdlib.h и равна 32’767 из чего следует, что случайные числа большого размера функцией rand не получить. Код ниже можно рассматривать как вариант решения этой проблемы:

int64_t A = rand(); A <<= 16; A |= rand(); A <<= 16; A |= rand(); A <<= 16; A |= rand(); 

Или просто:

int64_t A = (((((rand() << 16) | rand()) << 16) | rand()) << 16) | rand(); 

Реализация функции rand в старом C была проста и имела следующий вид:

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

Данная реализация имела не очень хорошее распределение чисел и ныне в C++ улучшена. Так же стандартная библиотека C++ предлагает дополнительные способы получения случайного числа, о которых ниже.

С++11 STL random

Данный сорт рандома появился в C++11 и представляет из себя следующий набор классов: minstd_rand, mt19937, ranlux, knuth_b и разные их вариации.

Чтобы последовательность случайных чисел не повторялась при каждом запуске программы, задают «зерно» псевдослучайного генератора в виде текущего времени или, в случае с некоторыми ретро (и не только) играми — интервалы между нажатиями клавиш с клавиатуры/джойстика. Библиотека random же предлагает использовать std::random_device для получения зерна лучше чем от time(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 random могут работать быстрее чем rand(), но давать менее качественную последовательность случайных чисел.

PRNG — Pseudo-random Numbers Generator

Можете считать это название — синонимом линейного конгруэнтного метода. PRNG алгоритмы похожи на реализацию rand в 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-bit рандом в эмуляторе 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 от Joe Wingbermuehle

Если вам интересно написание программ под машины с зилогом, то представляю вашему вниманию алгоритм от Joe Wingbermuehle, который легко можно переписать и под другие ассемблеры (соре, но в хабре нет красивой подсветки для асм кода):

; 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

В исходниках игры Дум есть такой интересный файл под названием 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[]; } 

; табличный рандом (как в 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 

Конечно же это ни какой не рандом и последовательность случайных чисел легко предугадать даже на уровне интуиции в процессе игры, но работает всё это крайне быстро. Если вам не особо важна криптографическая стойкость и вы хотите что-то быстро генерирующее «типа-рандом», то эта функция для вас.

RDRAND

Некоторые современные процессоры способны генерировать случайные числа с помощью одной ассемблерной команды — RDRAND. Для использования этой функции в C++ вы можете вручную прописать нужные инструкции ассемблерными вставками или же в GCC подключить файл immintrin.h и выбрать любую из вариаций функции _rdrandXX_step, где XX означает число бит в регистре и может быть равно 16, 32 или 64.

#include <immintrin.h>  unsigned val; _rdrand32_step(&val); 

Если вы увидите ошибку компиляции, то это значит, что вы не включили флаг -mrdrnd или ваш компилятор/процессор не поддерживает эту инструцию. Возможно это самый быстрый генератор случайных чисел, но есть вопросы в его криптографической стойкости, так что думайте.

Концовка

Класс std::minstd_rand из библиотеки STL random работает быстрее обыкновенного rand() и может стать его альтернативной заменой, если вас не особо волнует длинна периода в minstd. Возможны различия в работе этих функций в Windows и Unix’ах.

Инфа по теме

• Статья рассказывающая о C++11 random и некоторых особенностях работы с ним: Генерация случайных чисел в Modern C++
• Какие вообще есть генераторы в STL random. ссыль
• Вики статья про XorShift с разными реализациями: тык
• Гит эмулятора z26. Код рандома в файле c_pitfall2.c: гит
• Генератор рандома в Думчике: гит

P.S. Моя первая статья. Напишите что лишнее, чего добавить/убавить