Как работает рандом в программировании

Реализация функции 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 #include 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

Однажды мне пришлось сделать реализацию этого алгоритма для 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 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: гит
• Генератор рандома в Думчике: гит

Как работает рандом в программировании

Комментарии

Популярные По порядку
Не удалось загрузить комментарии.

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

Математика для программиста: советы, разделы, литература

Наверняка вы задумывались над вопросом: нужна ли математика программисту? И если нужна, то как "приручить" эту самую математику?

13 ресурсов, чтобы выучить математику

Среди разработчиков часто возникают споры о том, необходимо ли изучать математику. Если вас мучает ее незнание, то скорее читайте нашу статью.

4 книги, которые разбудят в вас математика

Программисту без математики никуда, даже если вы еще сомневаетесь в этом. Однако понять ее, не имея необходимых знаний и желания, достаточно сложно.

Arduino.ru

Функция random() возвращает псевдослучайное число.

Синтаксис

random(max) random(min, max)

Параметры

• min: нижняя граница случайных значений, включительно. (опционально)
• max: верхняя граница случайных значений, не включительно.

Возвращаемое значение

Случайное число между min и max-1. (long)

Замечание по использованию

Если при каждом запуске программы необходимо получать разные последовательности значений, генерируемых функцией random(), то необходимо инициализировать генератор псевдослучайных чисел со случайным параметром. Например, можно использовать значение, отдаваемое функцией analogRead() c неподключенного порта вход/выхода.

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

Пример

long randNumber; void setup() < Serial.begin(9600); // если порт 0 неподключен, то генератор псевдослучайных чисел // будет инициализироваться функцией randomSeed() со случайного // значения при каждом запуске программы из-за "шума" на порту randomSeed(analogRead(0)); >void loop() < // выводим случайное число из диапазона 0..299 randNumber = random(300); Serial.println(randNumber); // выводим случайное число из диапазона 10..19 randNumber = random(10, 20); Serial.println(randNumber); delay(50); >

Как работает рандом в программировании

Модуль random управляет генерацией случайных чисел. Его основные функции:

• random() : генерирует случайное число от 0.0 до 1.0
• randint() : возвращает случайное число из определенного диапазона
• randrange() : возвращает случайное число из определенного набора чисел
• shuffle() : перемешивает список
• choice() : возвращает случайный элемент списка

Функция random() возвращает случайное число с плавающей точкой в промежутке от 0.0 до 1.0. Если же нам необходимо число из большего диапазона, скажем от 0 до 100, то мы можем соответственно умножить результат функции random на 100.

import random number = random.random() # значение от 0.0 до 1.0 print(number) number = random.random() * 100 # значение от 0.0 до 100.0 print(number)

Функция randint(min, max) возвращает случайное целое число в промежутке между двумя значениями min и max.

import random number = random.randint(20, 35) # значение от 20 до 35 print(number)

Функция randrange() возвращает случайное целое число из определенного набора чисел. Она имеет три формы:

• randrange(stop) : в качестве набора чисел, из которых происходит извлечение случайного значения, будет использоваться диапазон от 0 до числа stop
• randrange(start, stop) : набор чисел представляет диапазон от числа start до числа stop
• randrange(start, stop, step) : набор чисел представляет диапазон от числа start до числа stop, при этом каждое число в диапазоне отличается от предыдущего на шаг step

import random number = random.randrange(10) # значение от 0 до 10 не включая print(number) number = random.randrange(2, 10) # значение в диапазоне 2, 3, 4, 5, 6, 7, 8, 9 print(number) number = random.randrange(2, 10, 2) # значение в диапазоне 2, 4, 6, 8 print(number)

Работа со списком

Для работы со списками в модуле random определены две функции: функция shuffle() перемешивает список случайным образом, а функция choice() возвращает один случайный элемент из списка:

numbers = [1, 2, 3, 4, 5, 6, 7, 8] random.shuffle(numbers) print(numbers) random_number = random.choice(numbers) print(random_number)