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



В этой статье вы увидите самые разнообразные велосипеды алгоритмы для генерации случайных чисел.

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


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

C++ rand


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

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 случайных бита


Реализация функции 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[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++ вы можете вручную прописать нужные инструкции ассемблерными вставками или же в 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. Моя первая статья. Напишите что лишнее, чего добавить/убавить




Комментарии (17):

  1. sinc
    /#21551614

    Генератор Фибоначчи. Просто, удобно, надежно, быстро. Используется в классе Random в .NET

  2. dvserg
    /#21551712

    Не ручаюсь за достоверность, но в Спектрумах вроде бы был специальный порт 255 для чтения «случайных» чисел с пассивной шины данных.

    • da-nie
      /#21552446

      Там был регистр регенерации динамической памяти R у Z80. Собственно, в вышеприведённом алгоритме ld a,r и используется.

  3. vitaliy31
    /#21552402

    Я далек от темы программирования микроконтроллеров, потому мне было бы интересно узнать что-нибудь об области применения ДПСЧ в ней.


    Возможно, не помешала бы более конкретная постановка задачи:


    • Везде, кроме, кроме C++ rand, идет речь о розыгрыше равномерного распределения чисел с плавающей точкой на открытом или закрытом множестве от 0 до 1, а не какого-либо другого. В C++ rand на выходе целое число — это же другая задача?
    • По области применения ДПСЧ часто делятся на криптографические и вычислительные (метод Монте-Карло). От криптографических датчиков в первую очередь требуется непредсказуемость последовательности (сложность определения алгоритма генерации по полученной последовательности), от вычислительных — близость статистических характеристик (мат. ожидание, дисперсия, корреляции и т.п.) получаемой последовательности к теоретическим значениям и быстродействие (критично). Например, PRNG — исключительно вычислительный датчик, и его использование для задач шифрования не подходит.

    На микроконтроллерах вряд ли делаются расчеты Монте-Карло, но вот на криптографическую стойкость/нестойкость приведенных датчиков, возможно, следовало бы указать.

    • CryptoPirate
      /#21556216

      ДПСЧ… От криптографических датчиков..

      Может вы о ГПСЧ (?) Генератор ПсевдоСлучайных Чисел, не датчик.

      От криптографических датчиков в первую очередь требуется непредсказуемость последовательности (сложность определения алгоритма генерации по полученной последовательности)

      Нет, для криптографически стойких генераторов требования не такие.
      Если по простому, то в хороших криптостойких генераторах: алгоритм открыт, неизвестен только ключ (зерно / seed), наблюдая за работой генератора нельзя предсказать следующее число (с большой вероятностью) и нельзя найти ключ.

      На микроконтроллерах вряд ли делаются расчеты Монте-Карло, но вот на криптографическую стойкость/нестойкость приведенных датчиков, возможно, следовало бы указать.

      Всё просто: все алгоритмы из этой статьи не подходят для криптографии.

      • vitaliy31
        /#21556246

        Если по простому, то в хороших криптостойких генераторах: алгоритм открыт, неизвестен только ключ (зерно / seed), наблюдая за работой генератора нельзя предсказать следующее число (с большой вероятностью) и нельзя найти ключ.

        Имел в виду алгоритм вместе со всеми своими параметрами — то, что нужно для восстановления всей последовательности по какому-то известному участку.


        Всё просто: все алгоритмы из этой статьи не подходят для криптографии.

        Согласен. Но для чего же они подходят? Это загадка, но, похоже, лишь для одного меня.
        Вопрос, разумеется, адресован главным образом к автору.

  4. da-nie
    /#21552464

    Автомат Вольфрама с правилом 30 забыли. :)

  5. Imp5
    /#21555196

    RAND_MAX описана в файле stdlib.h и равна 32'767

    Нет. Значение зависит от платформы. Например, на современном Линуксе её значение 2147483647.

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

    Так нельзя писать по двум причинам:
    1. Сдвиг на 16 бит, хотя минимальное значение RAND_MAX 32767, а это 15 бит.
    2. Если RAND_MAX больше 65535, то в числе будет больше единичных битов, для объединения надо использовать xor.

    • esaulenka
      /#21555902

      Так нельзя писать по двум причинам:

      По трём. Есть большая вероятность, что результат (rand()<<16) приведётся к 32-битному int (где-то, кстати, есть 64-битный инт?). Ещё один сдвиг на 16 от него ничего не оставит.

      • Imp5
        /#21560774

        Слона-то я и не заметил :)

    • AtariSMN82
      /#21571104

      Хорошее замечание, исправил этот момент в статье

  6. alexwortega
    /#21555868

    compsciclub.ru/courses/csseminar/2020-spring/classes/5758
    Кстати вот статья про генератор случайных чисел

  7. esaulenka
    /#21555888

    Алгоритм из дума уж больно похож на https://xkcd.com/221/
    :-)

  8. esaulenka
    /#21555986

    использовать std::random_device для получения зерна лучше чем от time(NULL), однако в случае с компилятором MinGW в Windows функция практически не работает

    Вот на эту тему хотелось бы подробностей.
    Пока что нагуглилось что оно RESOLVED FIXED
    https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85494
    Опс. Там target=10.0