Проблема с рандом% 100 для генерации случайных чисел в C

Question

Итак, у меня есть домашнее задание, и нам нужно сгенерировать случайные числа от 1 до 100 в C. У меня есть рабочий пример с int i = rand ()% 100; Но в соответствии с домашним заданием, которое является технически неправильным, которое я действительно не понимаю. Домашнее задание объясняется следующим образом

"1.1 Мы используем генератор случайных чисел для имитации времени прибытия шины. ===> функция rand (). Функция rand () возвращает псевдослучайное число от 0 до RAND_MAX (2 ^ 31-1 в linux). Чтобы сгенерировать случайное число, rn, между 0,0 и 1,0; rn = rand () / RAND_MAX. (Кстати, многие люди делают ниже, например, для создания двухзначных случайных чисел. R_num = rand ()% 100; так как% 100 от 0 до 99. Однако это неверно. Правильный способ генерирования случайного числа из 2 цифр: разделить 0-RAND_MAX на 10 интервалов и посмотреть, куда падает случайное число. Интервал времени равен = RAND_MAX / 100 Затем сопоставьте его с одним из 0 - 99 следующим образом: 0 1 2 3 ......... 99 0 это 2 * это 3 * это 99 * это к RAND_MAX Если rand () возвращает число между (12 * it) и (13 * it), случайное число из 2 цифр равно 12.) "

Я надеялся, что кто-нибудь попытается объяснить, о чем идет речь, я на самом деле не ищу примеры кода, просто чтобы понять проблему.

Answer 1

Есть несколько проблем, связанных с работой оператора по модулю. a % b эффективно дает вам остаток, когда вы делите a на b. Итак, давайте предположим, что мы вычисляем числа по модулю 4. Давайте также предположим, что RAND_MAX = 6, потому что я действительно не хочу, чтобы в моей таблице было 32768+ строк.

  a | a % 4
------------
  0 | 0
  1 | 1
  2 | 2
  3 | 3
  4 | 0
  5 | 1
  6 | 2

Так что, если вы используете свой подход для генерации случайных чисел от 1 до 4, у вас есть две проблемы. Во-первых, простой: вы генерируете числа от 0 до 3, а не от 1 до 4. Результат оператора по модулю всегда будет между 0 и модулем.

Другая проблема более тонкая. Если RAND_MAX не делится равномерно на модуль, вы не получите одинаковую вероятность каждого числа. В нашем примере есть 2 способа сделать 0-2, но только 3. Таким образом, 3 будет происходить в ~ 14,3% времени, а каждое другое число будет происходить в ~ 28,6% времени. Чтобы получить равномерное распределение, вам нужно найти способ справиться со случаями, когда RAND_MAX не делится равномерно.

Answer 2

Вы можете найти соответствующий код на SO.Например, приведенный ниже код rand_int() основан на коде для целых чисел в ответе на Правильна ли эта реализация на С шаффла Фишера-Йейтса? (и, в частности, ответ от Roland Illig ):

static size_t rand_int(size_t n)
{
    size_t limit = RAND_MAX - RAND_MAX % n;
    size_t rnd;

    while ((rnd = rand()) >= limit)
        ;
    return rnd % n;
}

Идея состоит в том, что вы вычисляете и игнорируете большие значения, возвращаемые rand(), которые приведут к смещенным результатам.Когда возвращается одно из больших значений, вы игнорируете его и пробуете следующее значение.Для этого редко понадобится более двух вызовов rand().

Некоторые внешние ссылки в Массив Shuffle в C могут оказаться полезными.

Answer 3

RAND_MAX обычно 2^31 - 1, поэтому оно равно 2147483647.

Но давайте для простоты предположим, что у нас очень странная система с RAND_MAX = 100 (так что rand() можетвернуть 0 в 100, это 101 число).И давайте предположим, что функция rand() имеет идеальное равномерное распределение .

Теперь, какова вероятность rand() % 100?Числа от 1 до 99 имеют одинаковую вероятность, то есть 1/101.Но 0 имеет вероятность 2/101, потому что когда rand() возвращает 0 и когда rand() возвращает 100, выражение rand() % 100 будет равно 0.Так что 0 может приходить чаще, чем любые другие числа, фактически в два раза чаще.Таким образом, наше распределение двузначных чисел с rand() % 100 не является равномерным.

Теперь текст предлагает решение проблемы.Предлагаемое решение состоит в том, чтобы разбить область от 0 до RAND_MAX на 100 четных частей, чтобы числа в каждой части имели одинаковую вероятность.Затем бросьте rand() и посмотрите, в каком регионе закончился номер.Если RAND_MAX равно 2147483647 и мы, например, получаем число 279172968, мы видим, что оно заканчивается в 13-й области - между RAND_MAX / 100 * 13 = 279172868 и RAND_MAX / 100 * 14 = 300647704.

Решение также имеет недостатки, так какмы можем видеть, что невозможно разделить 0 на RAND_MAX на 100 четных частей, когда RAND_MAX % 100 не равно 0.

Я чувствую, что единственное жизнеспособное решение - отбросить все числабольше RAND_MAX / 100 * 100 (используется целочисленная арифметика C).Остальные числа будут иметь равномерное распределение, а максимум будет делиться на 100, поэтому с остальными мы можем просто rand() % 100.Вот как то так:

int get_2_digit_number() {
      int r = 0;
      while (1) {
          r = rand();
          if (r > (RAND_MAX / 100 * 100)) { 
              continue;
          }
          break;
      }
      return r % 100;
}