Получить значения из нескольких распределений с помощью одного рулона генератора

Question

Получить значения из нескольких распределений с помощью одного рулона генератора

Я пытаюсь реализовать Метод псевдонимов, также описано Вот. Это алгоритм, который позволяет делать выборки из взвешенных N-сторонних кубиков в O (1).

Алгоритм требует генерации двух значений:

Равномерно распределенное целое число i в [0, N]
Равномерно распределенный реал y в [0, 1)

В документе указано, что эти два числа могут быть получены одним действительным числом x между [0, N), От x затем можно получить два значения как:

i = floor(x)
y = x - i

Теперь другие реализации, которые я видел, требуют генератора случайных чисел два раза, один для генерации i и один для генерации y, Учитывая, что я использую довольно дорогой генератор (std::mt19937) и что мне нужно пробовать много раз, мне было интересно, был ли лучший подход с точки зрения производительности при сохранении качества результата.

Я не уверен, что с помощью uniform_real_distribution чтобы генерировать x имеет смысл, как будто N большой тогда yРаспределение будет становиться более разреженным doubleы не распределены равномерно. Может быть, есть способ вызвать двигатель, получить случайные биты, а затем сгенерировать i а также y от них напрямую?

1

c++c++17 entropy random

Решение

Другие решения

У меня была похожая проблема, и я расскажу вам, как я решил ее в моем случае. Это может быть применимо к вам или нет, но вот история

Я не использовал какой-либо 32-битный ГСЧ. В основном, нет 32-битной платформы и программного обеспечения для заботы. Так что я использовал станд :: mt19937_64 в качестве базового генератора. Один 64-битный неподписанный int на вызов. Позже я попытался использовать один из 64-битных RNG PCG, в целом быстрее, хороший результат.
верхний N биты, которые будут использоваться непосредственно для выбора из таблицы (кости в вашем случае). Вы можете страдать от смещения по модулю, поэтому мне удалось расширить таблицу, чтобы получить точную степень 2 (2¹⁰ в моем случае 10 бит для выборки индекса)
Оставшиеся 54 бита были использованы для получения равномерного двойного случайного числа по предложению С. Винья.
Если вам нужно более 11 бит для индекса, вы можете либо жить с пониженной случайностью в мантиссе, либо заменить double y с тщательно обработанным целочисленным сравнением.

Вдоль линий, какой-то псевдокод (не проверено!)

uint64_t mask = (1ULL << 53ULL) - 1ULL;

auto seed{ 98765432101ULL };
auto rng = std::mt19937_64{seed};

for (int k = 0; k != 1000; ++k) {
auto rv = rng();
auto idx = rv >> uint64_t(64 - 10); // needed only 10 bits for index
double y = (rv & mask) * (1. / (1ULL << 53ULL)); // 53 bits used for mantissa
std::cout << idx << "," << y << '\n';
}

Ссылка на целочисленное двойное преобразование S.Vigna для RNG: http://xoshiro.di.unimi.it/, в самом конце страницы

1

Источник

Accepted Answer

Вы правы, с их методом распределения y будет становиться все менее и менее равномерным с увеличением N,

На самом деле, для N выше 2 ^ 52 y будет точно 0, так как все числа выше этого значения являются целыми числами для двойной точности. 2 ^ 52 составляет 4,503,599,627,370,496 (4,5 квадриллиона).

Это не имеет значения для разумных значений N хоть. Вы должны быть в порядке, если ваш N менее 2 ^ 26 (67 миллионов), интуитивно. У твоего кубика нет астрономического количества сторон?

1