# Примитивные и грязные генераторы случайных чисел

## Генераторы случайных чисел, поставляемые системой

В стандарте ANSI-C имеется функция rand(), выдающая равномерно распределенное число от 0 до RAND_MAX, и связанная с ней функция srand(), производящая начальную установку счетчика. Описание в файле <stdlib.h>. Почти все подобные генераторы используют рекуррентную последовательность
I(n+1)=(a*I(n)+c)(mod m).
Число a называется мультипликатором, число c инкрементом, а число m - модулем.

Такой выбор может послужить серьезным ограничением на статистические свойства последовательности случайных чисел. Кроме того, в большинстве случаев RAND_MAX=35767, что значительно меньше, чем диапазон изменения целых чисел. В некоторых испытаниях теория рекомендует 106 - 109 случайных проб, но, пользуясь подобным счетчиком, можно получить не более RAND_MAX одинаковых случайных чисел, т.е. в 30 тыс.- 30 млн. раз меньше рекомендуемого.

Генератор ANSI-C был опубликован комиссией как "пример". Мы его тоже приводим, но как "не рекомендованный" для серьезных приложений.

    /* (в модуле stdlib.h) */
    #define RAND_MAX 32767

    /* "пример" от комитета ANSI-C */
    unsigned long next=1;

    int rand(void) {
     next=next*1103515245+12345;
     return((unsigned int)(next/65536)%32768);
    }

    void srand(unsigned int seed) {
     next=seed;
    }

Мультипликатор и инкремент этого примера (который, скорее всего и поставляется со стандартной библиотекой C) не являются оптимальными. Об оптимальных константах для такого рода последовательностей ниже.

## Быстрые и грязные генераторы случайных чисел, отличные от "стандарта"

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

    Генерация случайного действительного числа, равномерно распределенного
    от 0 до 1 и целого, равномерно распределенного от jlow до jhigh.

    static unsigned long iran;
    unsigned long rand_a,rand_c,rand_m;
    float fran;
    int jran;
    ...................
    /* floating-point fran uniformly from 0 to 1 */
    iran=(iran*rand_a+rand_c)%rand_m;
    fran=(float)iran/(float)rand_m;
    ..................
    /* integer jran between jlow and jhigh */
    iran=(iran*rand_a+rand_c)%rand_m;
    jran=jlow+((jhigh-jlow+1)*iran)/im;

Ниже приводятся оптимальные значения коэффициентов rand_a, rand_c, rand_m для различного значения числа значащих бит в беззнаковом целом.

bits | rand_m | rand_a | rand_c
20 | 6075 | 106 | 1283
21 | 7875 | 211 | 1663
22 | 7875 | 421 | 1663
23 | 6075 | 1366 | 1283
6635 | 936 | 1399
11979 | 430 | 2531
24 | 14406 | 967 | 3041
29282 | 419 | 6173
53125 | 171 | 11213
25 | 12960 | 1741 | 2731
14000 | 1541 | 2957
21870 | 1291 | 4621
31104 | 625 | 6571
139968 | 205 | 29573
26 | 29282 | 1255 | 6173
81000 | 421 | 17117
134456 | 281 | 28411
27 | 86436 | 1093 | 18257
121500 | 1021 | 25673
259200 | 421 | 54773
28 | 117128 | 1277 | 24749
121500 | 2041 | 25673
312500 | 741 | 66037
29 | 145800 | 3661 | 30809
175000 | 2661 | 36979
233280 | 1861 | 49297
244944 | 1597 | 51749
30 | 139968 | 3877 | 29573
214326 | 3613 | 45289
714025 | 1366 | 150889
31 | 134456 | 8121 | 28411
259200 | 7141 | 54773
32 | 233280 | 9301 | 49297
714025 | 4096 | 150889

## Самый быстрый генератор для 32-битового представления целых и действительных чисел.

В большинстве случаев, число типа unsigned long имеет 32 бита. В этом случае для генерации числа в диапазоне 0 - 232-1 достаточно простого умножения на мультипликатор и сложения с инкрементом. Деление по модулю будет произведено автоматически при переполнении. Значения мультипликатора и инкремента для этого случая получены в исследованиях D. Knuth и H.W. Lewis.

    /* генерация целого числа от 0 до 0xFFFFFFFF. */
    static unsigned long iran;
    ...........
    iran=1664525L*iran+1013904223L;

Для реализации на этой основе очень быстрого генератора равномерного распределения действительных чисел от 0 до 1 важно, что floating-point single precision numbers (тип float) в большинстве случаев представлены также 32 битами. Кроме того, во многих случаях (включая SUN, ALPHA, Silicon Graphics и IBM PC) представление этого числа отвечает одному стандарту IEEE. Для машины VAX это не так. Грязным трюком, позволяющим избегнуть деления на действительное число, является маскировка экспоненты и дальнейшее вычитание из числа единицы. Необходимые коэффициенты в программе приведены для IEEE (по умолчанию) и для VAX.

    static unsigned long iran;
    unsigned long temp;
    float fran;
    ..........
    #if !defined(VAX)
     static unsigned long jflone=0x3f800000;
     static unsigned long jflmsk=0x007fffff;
    #else
     static unsigned long jflone=0x00004080;
     static unsigned long jflmsk=0xffff007f;
    #endif
    ..........
    iran=1664525L*iran+1013904223L;
    temp=jflone|(jflmsk&iran);
    fran=(*(float *)&temp)-1.F;

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

Случайные числа
Индекс