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


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

В стандарте 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;

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


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