Пример кода rand (), ненужная проверка больше чем max? - PullRequest
Новая
       46

Пример кода rand (), ненужная проверка больше чем max?

5 голосов
/ 10 октября 2019

Я искал функцию int rand() из <stdlib.h> в C11, когда наткнулся на следующий cppreference-example для броска шестигранного кристалла. 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int main(void)
{
    srand(time(NULL)); // use current time as seed for random generator
    int random_variable = rand();
    printf("Random value on [0,%d]: %d\n", RAND_MAX, random_variable);
 
    // roll a 6-sided die 20 times
    for (int n=0; n != 20; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + rand()/((RAND_MAX + 1u)/6); // Note: 1+rand()%6 is biased
        printf("%d ",  x); 
    }
}

В частности, эта часть: 

[...]
        while(x > 6) 
            x = 1 + rand()/((RAND_MAX + 1u)/6); // Note: 1+rand()%6 is biased
[...]

Вопросы:

  1. Почему добавляется + 1u? Поскольку rand() это [0,RAND_MAX] Я предполагаю, что делает rand()/(RAND_MAX/6) -> [0,RAND_MAX/(RAND_MAX/6)] -> [0,6]? И поскольку это целочисленное деление (LARGE/(LARGE+small)) < 1 -> 0, добавление 1u дает ему требуемый диапазон [0,5]?

  2. Опираясь на предыдущий вопрос, предполагая, что [0,5], 1 + (rand()/((RAND_MAX+1u)/6)) должнотолько пройти через [1,6] и никогда не запускать второй цикл?

Бродил, чтобы посмотреть, вернул ли rand() float в какой-то момент, но это кажется довольно огромнымполомка в сторону старого кода? Я полагаю, что проверка имеет смысл, если вы добавите 1.0f вместо 1u, сделав это делением с плавающей запятой?

Пытаясь обернуть это вокруг себя, возникает ощущение, что я что-то упускаю ..

(Ps Это не основа для чего-то критически важного для безопасности, я просто изучаю стандартбиблиотека. Ds)

1 Ответ

5 голосов
/ 10 октября 2019

Код позволяет избежать смещения, гарантируя, что каждый возможный результат в [1, 6] является выходом точно такого же числа возвращаемых значений из rand.

По определению, rand возвращает intзначения от 0 до RAND_MAX. Таким образом, есть 1+RAND_MAX возможных значений, которые он может вернуть. Если 1+RAND_MAX не кратно 6, то его невозможно разбить на 6 точно равных интервалов целых чисел. Таким образом, код разбивает его на 6 равных интервалов, которые являются максимально большими, и один интервал фрагмента нечетного размера. Затем результаты rand отображаются в эти интервалы: первые шесть интервалов соответствуют результатам от 1 до 6, последний интервал отклоняется, и код повторяется.

Когда мы делим 1+RAND_MAXк 6 есть некоторый коэффициент q и некоторый остаток r . Теперь рассмотрим результат rand() / q:

  • Когда rand выдает число в [0, q -1], rand() / q будет равно 0.
  • Когда rand производит число в [ q , 2 q -1], rand() / q будет равно 1.
  • Когда rand производитчисло в [2 q , 3 q -1], rand() / q будет равно 2.
  • Когда rand создает число в [3 q , 4 q −1], rand() / q будет равно 3.
  • Когда rand выдает число в [4 q , 5 q −1], rand() / q будет равно 4.
  • Когда rand выдает число в [5 q , 6 q −1], rand() / q будет 5.
  • Когда rand выдает число, равное 6 q или больше, rand() / q будет равно 6.

Обратите внимание, что в каждом из первых шести интервалов есть ровно q чисел. В седьмом интервале возможные возвращаемые значения находятся в [6 q , RAND_MAX]. Этот интервал содержит r чисел.

Этот код работает путем отклонения этого последнего интервала: 

int x = 7;
while(x > 6) 
    x = 1 + rand()/((RAND_MAX + 1u)/6);

Всякий раз, когда rand производит число в этом последнем фрагментарном интервале, этоКод отклоняет его и пытается снова. Когда rand производит число в одном из целых интервалов, этот код принимает его и завершает работу (после добавления 1, так что результаты в x будут от 1 до 6 вместо 0 до 5).

Таким образом,каждый выход от 1 до 6 включительно сопоставляется с точно равным числом значений rand.

Это лучший способ получить равномерное распределение от rand в том смысле, что оно имеетнаименьшее количество отклонений, учитывая, что мы используем такую ​​схему. 1 Диапазон rand разделен на шесть интервалов, которые являются максимально большими. Оставшийся фрагментарный интервал нельзя использовать, поскольку остаток r меньше шести, поэтому неиспользуемые значения r не могут быть равномерно разделены на шесть желаемых значений для x.

Сноска

1 Это не обязательно лучший способ использовать rand для генерации случайных чисел в [1, 6] в целом. Например, из одного вызова rand с RAND_MAX, равным 32767, мы могли бы рассматривать значение как цифру 6, от 000000 до 411411. Если оно меньше 400000, мы можем взять последние пять цифр, которыекаждый из них равномерно распределен в [0, 5], и добавление одного дает нам желаемый результат [1, 6]. Если это в [400000, 410000), мы можем использовать последние четыре цифры. Если это в [410000, 411000), мы можем использовать последние три и так далее. Кроме того, иная отбрасываемая информация, такая как начальная цифра, может быть объединена в несколько вызовов rand, чтобы увеличить среднее число выходов, которые мы получаем за вызов, до rand.

...