Чит случайных чисел?
Для целей стохастического моделирования будет ли достаточен следующий алгоритм для получения 1 миллиона псевдослучайных десятичных чисел того же качества, что и простая команда rand(), которую можно найти на большинстве компьютерных языков? Суть алгоритма заключается в использовании десятичных десятичных псевдоромандов и расширении их до 1 миллиона качественных десятичных псевдорандов.
Обратите внимание, что ниже приведен только алгоритм, а не реальный код.
double rands[10] = {rand()}; /// initialize a vector of 10 quality pseudorands [0,1]
double expandedRands[1000000] = {0}; /// initialize a vector of size 1 million
for(int i = 0; i < 10; i++)
{
for(double j = 0; j < 100000; j++) /// j goes from zero to one hundred thousand
{
expandedRands[(100000 * i) + j] = rands[i] * abs((j - 0.5)/ 1000000);
}
}
РЕДАКТИРОВАТЬ: я понимаю, что человек мог бы ясно взглянуть на числа, сгенерированные из этого алгоритма, и знать, что они следуют шаблону, но реальный вопрос заключается в том, будет ли стохастическое моделирование работать так же, как если бы они питались этими числами, а не 1 миллионами rand(),
3 ответа
Ваш алгоритм не генерирует равномерное распределение.
expandedRands[(100000 * i) + j] = rands[i] * (j / 100000);
Во-первых, для каждого начального случайного значения 𝑖 вы генерируете 100000 значений в диапазоне [0,𝑖). Это явно искажает распределение в сторону более низких значений.
Кроме того, каждое значение в окончательных данных генерируется только из одного из начальных 10 значений, и все они равномерно распределены. Это дает немало информации наблюдателям и означает, что они смогут угадать больше значений в конечном массиве с довольно высокой вероятностью сделать правильные предположения.
Предположительно вам нужно растянуть 10 звонков на rand() в 1 000000 качественных случайных чисел, потому что rand() очень медленно (и, надеюсь, генерирует очень хорошие случайные данные взамен). В этих обстоятельствах я бы использовал результаты rand() как не что иное, как семя для хорошего, детерминированного pRNG.
Некоторый код, включая средства C++ для реализации этой идеи:
// initialize a vector of 10 quality pseudorands [0,RAND_MAX]
int rands[10];
for(int i = 0; i < 10; ++i) { rands[i] = rand(); }
std::seed_seq seeds(begin(rands), end(rands));
// seed_seq is from C++ and performs a standard RNG 'warm-up' sequence
// In other languages you'll simply implement a warm-up sequence yourself.
std::mt19937 eng(seeds);
// mt19937 is an implementation of a standard RNG.
// the seed_seq ensures a good initial state for producing random bits
// You can use whatever standard pRNG algorithm meets your quality/performance/size needs
// For example, if you need something faster and with a smaller state you could use a linear congruential engine such as minstd_rand0
std::uniform_real_distribution<double> dist(0.0, 1.0);
// a C++ object which takes random bits and produces random values with a good distribution.
// there are many different algorithms for doing this
double expandedRands[1_000_000];
for(int i = 0; i < 1_000_000; ++j) {
expandedRands[i] = dist(eng);
}
expandedRands теперь содержит миллион значений, равномерно распределенных в диапазоне [0.0, 1.0). При одинаковых начальных 10 случайных значениях вы получите одинаковые миллионы выходных значений, и любая разница во входных данных должна давать совершенно разные выходные данные.
Если вы растягиваете rand()результаты, потому что вам нужно что-то более распараллеливаемое, чем сериализованные вызовы rand()то, что вы можете сделать, это использовать десять rand() вызывает генерацию начальной последовательности, а затем использует ее для запуска нескольких независимых механизмов pRNG, которые могут работать на разных ядрах или в независимых экземплярах ядра GPGPU (если вы можете реализовать pRNG и дистрибутив в CUDA или как угодно).
int rands[10];
for (int i = 0; i < 10; ++i) { rands[i] = rand(); }
std::seed_seq seeds(begin(rands), end(rands));
std::mt19937 eng[10];
for (int i = 0; i < 10; ++i) { eng.seed(seeds); }
// now the engines can be used on independent threads.
PS Я знаю, что ваш код - всего лишь псевдокод, но я видел определенную ошибку в C, поэтому на всякий случай вы написали свой код таким образом из-за того же неправильного представления о C:
double rands[10] = {rand()};
Инициализатор в C не выполняет это выражение 10 раз и инициализирует каждый элемент с другим значением. Что происходит в C, так это то, что, когда инициализаторов меньше, чем элементов в массиве, инициализаторы, которые там находятся, присваиваются их соответствующим элементам (первый инициализатор первому элементу, второй инициализатор второму элементу и т. Д.), А затем остальные элементы инициализируются нулями. Так, например:
int x[10] = {0};
инициализирует весь массив нулями, но:
int x[10] = {1};
инициализирует первый элемент в один, а затем остальные в ноль.
Это не собирается генерировать 1 000 000 псевдослучайных чисел вообще.
Вы расширяете массив только из 10 "реальных" псевдослучайных чисел до 1 миллиона, используя сложение, умножение и вычитание.
В итоге у вас осталось только 10 случайных чисел.
Подумайте об этом, если функция системы rand() производит только двоичное значение, 1 или 0. Вероятность того, что вы получите rands[10] заполнены все нули: (0,5)^10, или около 0,098%.
Теперь с вашим expandedRands[(100000 * i) + j] = rands[i] * (j / 100000);, вы будете заполнять все 1 миллион чисел нулями, потому что rands[i] является 0, так rands[i] * (j / 100000) является 0,
Какова вероятность получения всех чисел в виде нулей, если вы действительно сгенерировали 1 000 000 чисел?
(0.5) ^ 1000000 = 0. У вас будет больше шансов выиграть лотерейный билет, который вы даже не купили, чем если бы это случилось хоть раз.
По мере того как j будет становиться все больше и больше, вы получите качественное случайное число i (j/100000=1).
Попробуйте построить график с помощью графика в Excel, и вы четко увидите, что вы сходитесь к своему случайному числу.