Статья предоставлена
(c) Nikitine Valeri F. 2000,
web: algorithm.narod.ru
В стандарте 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) не являются оптимальными.
Об оптимальных константах для такого рода последовательностей читайте в описаниях других генераторов.
|
