!Рандом

Описание

Для многих алгоритмов может понадобиться рандом, и в c++ он есть, но настоящим рандомом он не является, он также детерминирован, как и весь остальной код и поэтому он назван псевдорандомом. Все “рандомные” числа этой функции зависят только от сида, который вы задаете при инициализации. Устроены функции примерно так, мы берем стартовый сид умножаем его на какую-нибудь константу a, добавляем другую константу b и берем по нужному модулю. Этот алгоритм предположительно легко ломается, ведь для этого надо просто понять как остаток по модулю изменяется при одной итерации и чтобы сломать такое было сложнее, можно вместо констант a и b взять прошлые значения рандомной функции и тогда изменения на самом деле будет сложно предсказать.

Примеры

1. Стандартный rand плох для использования, ведь на разных реализациях компилятора максимальный допустимый выдаваемый элемент может быть маленьким, поэтому его пример я приводить сюда не буду.
2. Две версии хорошего рандома mt19937 для случайных чисел от $1$ до $2^{32}$ и mt19937_64 для случайных чисел от $1$ до $2^{64}$:

#include <random>
using namespace std;
mt19937 rnd_32(239);
mt19937 rnd_64(239);

3. Для получения случайного double числа на отрезке можно воспользоваться uniform_real_distribution, которое в себя принимает любой генератор и выдает случайные нецелые числа:

#include <random>
using namespace std;
mt19937 rnd_32(239);
uniform_real_distribution<> rnd_d(0, 1);
 
int main() {
	cout << rnd_d(rnd_32); // Выводит случайное число от 0 до 1
}

4. Для рандомного перемешивания массива, что часто ускоряет решения в методе отжига, можно использовать функцию shuffle, которая принимает в себя два указателя и генератор:

shuffle(arr.begin(), arr.end(), rnd_32);

Какие сиды использовать?

Для тестирования лучше всего использовать константный сид, ведь при неправильном ответе, если сид будет случайный, то тест не восстановить, а если будет конкретным, то можно будет перететить с ним после исправленияП баги, что будет полезно при написании стрестестов и отжига. Самое простое, что можно использовать, это время в секундах, получаемое командой time(NULL), но лучше использовать chrono::steady_clock::now().time_since_epoch().count() для подсчета в милиссекундах. Также, если компиляция происходит на unix системах, то можно воспользоваться внутренним рандомом random_device r_d, которые работает получше, ведь отдается системой. Также можно воспользоваться тем, что ссылка на байт памяти стоит случайно (uint64_t) new char выдает адрес недавно выделенной ячейки функции, но это может сломаться, если этот адрес при каждом запуске обнуляется и становится детерминированным.