Про рандом

---

Генератор псевдослучайных чисел (ГПСЧ) - программа, которая принимает некое стартовое значение, выполняет над ним определенные математические операции, чтобы конвертировать его в другое число, которое совсем не связано со стартовым. Затем программа берет полученное число и выполняет над ним теже математические операции, чтобы получить еще одно новое число и т.д.

Простейший ГПСЧ основан на свойстве переполнения unsigned int (при достижении максимального значения (UINT_MAX), следующее значение будет минимальным (UINT_MAX + 1 = 0), формула: uint % (UINT_MAX + 1), +1 для ноликов). Примерно так же был реализован rand() из cstdlib в первых версиях:

// static - локальная переменная не удаляется после выхода из блока

unsigned int pseudo_rand()
{
    static unsigned int seed = 4541; // стартовое значение
    seed = (8253729 * seed + 2396403);
    return seed % 32768;
}
// Подобная генерация называется Линейный Конгруэнтный Метод
// Минусы: маленький период (через сколько числа снова будут повторяться)

Встроенные генераторы cstdlib

• srand() - устанавливает передаваемое значение в качестве стартового
• rand() - генерирует следующее псевдослучайное число в диапазоне [0; RAND_MAX]
• RAND_MAX - константа из cstdlib

#include <iostream>
#include <cstdlib>

int main()
{
    srand(4541);
    std::cout << rand() << " ";
    return 0;
}

Понятно что весь псевдо рандом построен на стартовом значении и при каждом запуске такой программы будут генерироваться одни и теже значения. Для решения этой проблемы нужно каким-то образом рандомизировать стартовое значение, общепринятым решением являеться привязка к системному времени (В ретро играх использовали интервалы между нажатиями клавиш с клавиатуры/джойстика):

• time() - Unix time: возвращает сколько секунд прошло начиная с 01.01.1970

#include <iostream>
#include <cstdlib>
#include <ctime>

int main()
{
    srand(time(0)); 
    std::cout << rand();
    return 0;
}

Диапазоны

Самый простой способ (проблема: распределение не равномерное, вероятность получить число ближе к левой границе больше):

rand() % x         => [0; x)
rand() % (x-a)     => [0, x-a)
a + rand() % (x-a) => [a; x)

Достаточно равномерное (на сколько это позволяет rand()) распределение в диапазоне [0.0; 1.0]:

double(rand()) / RAND_MAX;

Теперь, используя равномерное распределение в диапазоне [0.0, 1.0] можно получить и другие диапазоны:

// Получаем случайное число [0.0; 1.0]
// [0.0; 1.0] * (max - min) = [0.0; max-min]
// [0.0; max-min] + min = [min; max]

int rand(int min, int max)
{
    static const double r = 1.0 / double(RAND_MAX);
    return int(rand() * r * (max - min) + min);
}

Рандомные числа в С++11

В С++11 добавили много нового функционала для генерации чисел, в том числе отличный алгоритм - Вихрь Мерсенна, а так же генераторы разных видов распределений (нормальное, равномерное, экспоненциальное…).

Вместо привязки к времени для стартового значения предлагают использовать std::random_device, однако стоит отметить что в случае с компилятором MinGW эта функция почти не работает как надо (можно использовать время как и раньше).

Вихрь Мерсенна:

#include <iostream>
#include <ctime>
#include <random>

int main()
{
    // инициализируем Вихрь Мерсенна случайным стартовым числом
    std::random_device rd;
    std::mt19937 mersenne(rd());

    std::cout << mersenne();
    return 0;
}