Можно ли использовать `rand()` в С++ для создания объективных логических значений?

Одним из распространенных дефектов генераторов случайных чисел является небольшое смещение в сторону меньших результатов (в основном небольшое смещение в сторону 0 в старших битах). Это часто происходит, когда перенос внутреннего состояния RNG в выходной диапазон выполняется с помощью простого мода, который смещен в сторону высоких значений, если только RAND_MAX не является делителем размера внутреннего состояния. Вот типичная реализация предвзятого отображения:

static unsigned int state;

int rand() {
   state = nextState(); /* this actually moves the state from one random value to the next, eg., using a LCG */
   return state % RAND_MAX;  /* biased */
}

Смещение возникает из-за того, что более низкие выходные значения имеют еще одно отображение под модом из состояния. Например, если состояние может иметь значения 0–9 (10 значений), а RAND_MAX равно 3 (значения 0–2), то результатом операции % 3 в зависимости от состояния

Output  State
0       0 3 6 9 
1       1 4 7
2       2 5 8

Результат 0 перепредставлен, потому что он имеет шанс быть выбранным 4/10 по сравнению с 3/10 для других значений.

В качестве примера с более вероятными значениями, если внутреннее состояние RNG является 16-целым числом, а RAND_MAX равно 35767 (как вы упомянули, это на вашей платформе), тогда все значения [0,6000] будут выведены для 3 разных значения состояния, но оставшиеся ~30 000 значений будут выведены только для 2 различных значений состояния — значительное смещение. Этот тип смещения может привести к тому, что значение вашего счетчика будет выше, чем ожидалось (поскольку меньшие, чем универсальные, результаты rand() благоприятствуют условию p_scaled >= 1.

Было бы полезно, если бы вы могли опубликовать точную реализацию rand() на вашей платформе. Если окажется, что это смещение в старших битах, вы можете устранить это, передав значения, полученные от rand(), через хорошую хэш-функцию, но лучший подход, вероятно, состоит в том, чтобы просто использовать высококачественный источник случайных данных. числа, например, Вихрь Мерсенна. У лучшего генератора также будет больший выходной диапазон (эффективный, более высокий RAND_MAX), что означает, что ваш алгоритм будет подвергаться меньшему количеству повторных попыток/меньшей рекурсии.

Даже если реализация среды выполнения Visual Studio страдает от этого дефекта, стоит отметить, что это, вероятно, было, по крайней мере частично, преднамеренным выбором дизайна — использование RAND_MAX, такого как 35767, которое является относительно простым по отношению к размеру состояния (обычно степени 2), гарантирует лучшая случайность младших битов, поскольку операция % эффективно смешивает биты старшего и младшего разрядов, а наличие смещенных/неслучайных битов младшего разряда на практике часто является более серьезной проблемой, чем небольшое смещение битов старшего разряда из-за вездесущности вызывающего rand() уменьшает диапазон с помощью %, который эффективно использует только младшие биты для модулей, которые являются степенями 2 (также очень распространены).

Я попробовал ваш код в Linux, и результаты были довольно приличными. Однако похоже, что вы находитесь в Windows, где RAND_MAX, вероятно, составляет около 32768. Я говорю, поскольку gcc жаловался на Linux, что RAND_MAX+1 приводит к целочисленному переполнению, поэтому мне пришлось добавить приведение.

Так что проблема, скорее всего, в том, что либо RAND_MAX слишком мал, либо реализация rand() в вашей системе не очень хороша.

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

/* change `rand()` to return two concatenated rands */
typedef long long rand_type; /* this type depends on your actual system, you might get away with `int` */
#define BIGGER_RAND_MAX ((RAND_MAX + 2) * RAND_MAX)
rand_type bigger_rand(void)
{
    return (rand_type)rand() * (RAND_MAX + 1) + rand();
}

А затем попробуйте свою программу с этим рандом, который имеет более высокий диапазон. Если проблема не устранена, скорее всего, дело в вашей далеко не случайной функции rand().

Примечание: ваш random_bool должен возвращать bool, а не double! Поскольку вы проверяете double на ноль, это также может быть источником проблемы, когда у вас есть ложные срабатывания, потому что двойное значение может быть не совсем нулем.

я думаю, что результат этой функции связан со значением RAND_MAX, в данном случае p = 1e-6, если RAND_MAX равен 9999, то это никогда не вернет true