Date Редакция Категория comp Теги C / Cpp

Часто можно встретить следующую рекомендацию по использованию функции rand, генерирующей случайные числа в C/C++:

  • создать "затравку" последовательности (псевдо)случайных чисел с помощью srand(time(NULL));
  • сгенерировать случайное число в диапазоне [0;N): rand() % N.

Получается примерно следующее

#include <stdio.h>
#include <stdlib.h> /* rand, srand */
#include <time.h>   /* time */

const int N = 10;
const int numProbes = 100;

int main()
{
    int i, r;

    srand(time(NULL));

    for (i = 0; i < numProbes; i++) {
        r = rand() % N;
        printf("%i\n", r);
    }

    return 0;
}

И если с "затравкой" все обстоит нормально, то использованное в примере масштабирование диапазона случайных чисел приводит к неравномерности их распределения.

Функция rand должна генерировать целые случайные числа в диапазоне [0;RAND_MAX], где RAND_MAX -- заданная константа, значение которой не может быть меньше 32767.

Предположим, что нам необходимы целые числа из диапазоне [0;10). 10 не делится нацело на 32768, поэтому весь диапазон разбивается на 3276 десятков + "излишек", состоящий из восьми чисел. В этом случае вероятность получить в результате 8 или 9 меньше, чем получить числа из диапазона [0;7].

Таким образом, метод rand() % N применим только тогда, когда N делит RAND_MAX+1 нацело. Если это условие не выполняется, то вероятность получить в результате случайное число из интервала [(RAND_MAX % N), N) меньше, чем число из интервала [0, (RAND_MAX % N)).

Для нашего примера возникшее нарушение равномерности невелико: на более чем 3000 полных десятков приходится 1 неполный, т. е. добавка составляет меньше 0.1%. К тому же, в ряде платформ значение RAND_MAX значительно больше, чем определенный стандартом минимум. Например, у меня в Xubuntu Linux RAND_MAX=2147483647, что еще более сглаживает неравномерность. И тем не менее она существует.

Более предпочтительным является подход, использующий вещественные числа. Например, для того, чтобы получить случайное число в диапазоне [0; 10) выполняем

int r = (10.0 / (RAND_MAX + 1)) * rand();

Выражение (10.0 / (RAND_MAX + 1)) будет конвертировано в константу с плавающей точкой, а все преобразование будет состоять из умножения на эту константу.

Для получение чисел из диапазона [-100; 100] (всего 201 значение):

int r = -100 + (201.0 / (RAND_MAX + 1)) * rand();

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



Комментарии

comments powered by Disqus