Автор: © Ken O. Burtch
Перевод: © Дмитрий Попков.

Внизу Научного Центра Онтарио в Торонто (Канада) расположено большое круговое устройство, сделанное из тонких прутов стали. Любознательные наблюдатели могут взять биллиардные шары, находяшиеся там для этой цели, и пустить их свободно по устройству. Шары со свистом летят по направляющим, с лязгом рикошетят от штырей, захватываются центробежной силой и поднимаются к потолку. В некоторых местах шары выбирают одну направляющую или другую совершенно случайно. Как получается, что эта несиловая конструкция, созданная по жесткому образцу, выдает непредсказуемые результаты?

Написание программ, использующих случайные числа, требует понимания методов оценки ошибки, теории вероятностей, статистики и других специализированных математических дисциплин.

Похоже на какую-то занудную чушь?

Случайные числа нужны для придания вашим программам эффекта неожиданности без вовлечения core dump.  Это настоящий полигон для захватывающих дух экспериментов.

Компьютеры не используют настоящие случайные числа.  Подобно машине с биллиардными шарами, компьютеры строги, ограничены правилами и логикой.  Для генерации действительно случайных чисел компьютер должен выбирать числа, порожденные реальными событиями.  Раньше людям приходилось катать 10-сторонний пронумерованный игральный кубик и составлять последовательность цифр для использования в программах.

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

Стандартная в Linux С-библиотека (stdlib.h) содержит две встроенные функции для случайных чисел.  Первая, rand(), возвращает случайную последовательность между 0 и RAND_MAX.  Если мы наберем

  printf( " rand() is %d\n", rand() );
  printf( " rand() is %d\n", rand() );
  printf( " rand() is %d\n", rand() );

rand() вернет подобные значения

  rand() is 1750354891
  rand() is 2140807809
  rand() is 1844326400

Каждое обращение вернет новое, случайно выбранное положительное целое число (типа integer).

Другая стандартная библиотечная функция random() вернет положительное длинное целое число (типа long integer).  В Linux и целочисленные, и длинные целые числа имеют одинаковый размер.  random() обладает и некоторыми другими свойствами, которые обсудим далее.

Существуют также и другие, уже устаревшие, функции для получения случайных чисел

  * drand()/erand() возвращает случайное двойное между 0..1.
  * lrand()/nrand() возвращает случайное длинное между 0 and 2^31.
  * mrand()/jrand() возвращает последовательность случайной длины.

Они обеспечивают обратную совместимость с другими клонами UNIX.

rand() и random(), конечно, совершенно бесполезны сами по себе и редко вызываются непосредственно. Не так часто мы ищем числа между 0 и действительно большим числом: числа должны принадлежать, в соответствии с поставленной проблемой, заданному диапазону.  Чтобы приручить rand(), его значения должны быть промасштабированы в приемлемом диапазоне, например между 0 и заданным максимумом.   Неплохо работает модульный оператор (%): когда число поделено, остаток между 0 и 1 меньше оригинала.  Добавление 1 к модулю дает искомый диапазон.

  int rnd( int max ) {
    return (rand() % max) + 1;
  }

Здесь одна линейная функция вернет числа между 1 и заданым максимумом.  rnd(10) вернет числа между 1 и 10, rnd(50) вернет числа между 1 и 50.  Реальные события могут моделироваться выбором соответствующих значений для получения определенных результатов.  Бросок монеты - это rnd(2)==1 для решки и rnd(2)==2 для орла  Бросок игрального кубика - rnd(6)+rnd(6)

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

Следующая тестовая программа генерирует 100 чисел между 1 и 10, считая как часто каждое число появляется в последовательности.  Если бы числа были совершенно равноправны, каждое из них появилось бы по 10 раз.

  int graph[11];
  int i;

  for (i=1; i<=10; i++)
      graph[i] = 0;
  for (i=1; i<=100; i++)
      graph[ rnd(10) ]++;
  printf( "for rnd(), graph[1..10] is " );
  for (i=1; i<=10; i++)
      printf( "%d " , graph[i] );
  printf( "\n" );

Запустив эту подпрограмму, мы получим следующее:

  for rnd(), graph[1..10] is 7 12 9 8 14 9 16 5 11 9

Функция rand() в Linux прилагает серьезные усилия, чтобы сгенерировать высококачественную случайную последовательность, и поэтому использует существенное количество процессорного времени.   Если необходимо быстро сгенерировать случайную последовательность среднего качества, используйте что-нибудь подобное:

unsigned int seed = 0;

int fast_rnd( int max ) {
  unsigned int offset = 12923;
  unsigned int multiplier = 4079;

  seed = seed * multiplier + offset;
  return (int)(seed % max) + 1;
}

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

Замена rnd на fast_rnd() в тестовых функциях все еще дает разумное приближение к rand()

  for fast_rnd(), graph[1..10] is 11 4 4 1 8 8 5 7 6 5

Seed -- это начальное значение, выданное генератору случайной последовательности, чтобы получить первое случайное чиcло.  Если вы присвоите seed определенное значение, последовательность чисел будет всегда повторяться, начиная с этого же самого чила.  Если вы, к примеру, пишете игру, вы можете установить seed в определенное значение и использовать fast_rnd(), чтобы расставлять "врагов" в определенном месте без фактического сохранения информации об их расположении.

  seed = room_number;
  num_enemy = fast_rnd( 5 );
  for ( enemy=1; enemy<=num_enemy; enemy++ ) {
      enemy_type[enemy] = fast_rnd( 6 );
      enemy_horizontal[enemy] = fast_rnd( 1024 );
      enemy_vertical[enemy] = fast_rnd( 768 );
  }

Seed для rand() в Linux устанавливается посредством srand(). Например,

  srand( 4 );

установит rand() seed в 4.

Существуют два способа управлять последовательностью в другой функции Linux - random().  Первый - srandom(), подобен srand(), устанавливает seed для random().

Второй способ актуален, если вы нуждаетесь в большей точности: Linux обеспечивает две функции, чтобы управлять быстродействием и точностью random().  С помощью initstate() вы можете задать random() и начальное число, и буфер для хранения промежуточных результатов.  Буфер может быть размером 8, 32, 64, 128 или 256.  Больший буфер даст более случайные числа, но потребует больше времени для расчетов.

  char state[256];                 /* 256 байт буфер */
  unsigned int seed = 1;         /* устанавливаем seed в 1 */

  initstate( seed, state, 256 );
  printf( "using a 256 byte state, we get %d\n", random() );
  printf( "using a 256 byte state, we get %d\n", random() );
  initstate( seed, state, 256 );
  printf( "resetting the state, we get %d\n", random() );

получаем

  using a 256 byte state, we get 510644794
  using a 256 byte state, we get 625058908
  resetting the state, we get 510644794

Вы можете переключать состояние random() посредством setstate() совместно srandom() для установки seed в определенное значение.
setstate() всегда возвращает указатель на предыдущее состояние.

  oldstate = setstate( newstate );

Если вы не изменяете seed при запуске программы, ваши случайные числа будут всегда те же самые.  Для создания изменяющейся случайной последовательности seed должно быть установлено в некоторое значение, взятое вне программы. Хороший прием - использование значения, возвращаемого функцией time(), использующей time.h.

  srand( time( NULL ) );

Так как время постоянно меняется, это даст вашей программе новую последовательность случайных чисел при каждом новом запуске.

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

Так каков же лучший метод перетасовки списка?  Разрезание печатных листов?  Сомневаюсь.  Обмен случайных элементов несколько тысяч раз?.   Эффективно, но медленно и не гарантирует, что все элементы будут иметь шанс на перемещение.   Лучше будет взять каждый элемент списка и поменять его местами с каким-нибудь другим.   Например, предположим, что мы имеем список из 52 игральных карт с номерами от 0 до 51.  Для перетасовки карт сделаем следующее:

  int deck[ 52 ];
  int newpos;
  int savecard;
  int i;

  for ( i=0; i<52; i++ )
      deck[i] = i;
  printf( "Deck was " );
  for ( i=0; i<52; i++ )
      printf( "%d ", deck[i] );
  printf( "\n" );
  for ( i=0; i<52; i++ ) {
      newpos = rnd(52)-1;
      savecard = deck[i];
      deck[i] = deck[newpos];
      deck[newpos] = savecard;
  }
  printf( "Расклад таков: " );
  for ( i=0; i<52; i++ )
      printf( "%d ", deck[i] );
  printf( "\n" );

В результате получим расклад до и после:

  Было 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
  Стало 35 48 34 13 6 11 49 41 1 32 23 3 16 43 42 18 28 26 25 15 7 27 5 29 44 2 47 38 39 50 31 17 8 14 22 36 12 30 33 10 45 21 46 19 24 9 51 20 4 37 0 40

Люди, знакомые со статистикой, знают, что многие реальные жизненные события не подчиняются закону равномерного распределения.  Первый капитальный ремонт автомобиля, например, может потребоваться между 5 и 9 годом после приобретения, но это чаще случается на 7-й год.   Любой год в этом диапазоне вероятен, но наибольшую вероятность имеет середина диапазона.

Небольшие неожиданные события подобно этому описываются колоколообразной кривой Гаусса (называемой нормальным распределением в статистике).  Создание случайных чисел, удовлетворяющих таким сложным условиям, может показаться неординарной задачей, но в действительности это не так.  Наша функция rnd() уже производит неплохие равномерно распределенные "неожиданные" события, нам не нужны талмуды по статистике с формулами для генерации нормально распределенных случайных чисел.  Все что нужно, так это несколько раз вызвать rnd() и взять среднее значение, моделируя нормальное распределение.

int normal_rnd( int max ) {
  return (rnd( max ) + rnd( max ) + rnd( max ) + rnd( max ) +
         rnd( max ) + rnd( max ) + rnd( max ) + rnd( max ) ) / 8;

}

Используя normal_rnd() в тестовой функции, мы получаем значения, которые распределены в средней точке между 1 и max:

  for normal_rnd(), graph[1..10] is 0 0 4 26 37 23 10 0 0 0

Нормальные случайные числа могут быть использованы, чтобы сделать игру более правдоподобной, делая поведение врагов более устойчивым.

Для чисел, искаженных к концу диапазона, мы можем создать low_rnd() с приоритетом около 1.

  int low_rnd( int max ) {
    int candidate;

    candidate = rnd( max );
    if ( rnd( 2 ) == 1 )
       return candidate;
    else if ( max > 1 )
       return low_rnd( max / 2 );
    else
       return 1;
  }

В каждой рекурсии low_rnd() делит диапазон пополам.   Вычитая наименьшее случайное число от наибольшего в диапазоне, мы можем записать соответствующие значения high_rnd(), где приоритет отдается числам, расположенным около max:

  int high_rnd( int max ) {
    return max - low_rnd( max ) + 1;
  }

Искажения легко обнаруживаются с помощью тестовой программы:

  для low_rnd(), graph[1..10] is 36 15 11 8 9 3 4 3 3 8
  для high_rnd(), graph[1..10] is 4 5 8 5 4 10 6 10 14 34

Случайные ветви в логике могут быть получены с помощью функции odds()

  int odds( int percent ) {
       if ( percent <= 0 )
          return 0;
       else if ( percent > 100 )
          return 1;
       else if ( rnd( 100 ) <= percent )
          return 1;
       return 0;
  }

Эта функция возвращает значение "Истина" в течение указанного процент от заданного времени, тем самым облегчая объединение с условными операторами типа if.

  if ( odds( 50 ) )
    printf( "Пещера не обрушилась!\n" )
 else
   printf( "О, черт - не повезло! Вы погребены заживо в груде камней.\n" );

Стандартые в С-библиотеке функции rand() и random() обеспечивают программную генерация равномерно распределенных случайных чисел.  Последовательность и точность могут управляться другими библиотечными функциями и распределение чисел может быть изменено простыми функциями.  Случайные числа могут добавить непредсказуемость программе и, конечно, это отправная точка для игрового азарта в компьютерных играх.