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

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

I(n+1)=(a*I(n)+c)(mod m).

Число a называется мультипликатором, число c инкрементом, а число m - модулем.

Такой выбор может послужить серьезным ограничением на статистические свойства последовательности случайных чисел. Кроме того, в большинстве случаев RAND_MAX=35767, что значительно меньше, чем диапазон изменения целых чисел. В некоторых испытаниях теория рекомендует 10⁶ - 10⁹ случайных проб, но, пользуясь подобным счетчиком, можно получить не более 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) не являются оптимальными. Об оптимальных константах для такого рода последовательностей читайте в описаниях написано далее.

7.4. Генератор с малым кодом

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

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

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

static unsigned long iran;

unsigned long rand_a,rand_c,rand_m;

floatfran;

intjran;

...................

/* действительные числа между 0 и 1 */

iran=(iran*rand_a+rand_c)%rand_m;

fran=(float)iran/(float)rand_m;

..................

/* целые числа между jlow и 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

генератор очень простой. Это его основное достоинство. На 80с51 одна "случайная" величина генерируется за 3мс примерно. Это совсем неплохой результат. Для целей однопроцессорной ЭВМ очень хороший результат. Генерация достаточно равномерная в заданном диапазоне. У меня при генерации чисел от 0 до 255 вероятности следующие

0,055; 0,067; 0,055; 0,091; 0,059; 0,047; 0,083; 0,063; 0,075; 0,083; 0,047; 0,063; 0,059; 0,0002; 0,063; 0,051.