|
Страница 25 из 37
Генераторы случайных чисел Технически термин "генератор случайных чисел" - это абсурд;
числа само по себе не являются случайными. Например, 100 - это
случайное число? А 25? Что в действительности означает этот тер-
мин, так это то, что создается последовательность чисел, появляю-
щихся случайным образом. Это порождает более сложный вопрос: что
такое последовательность случайных чисел? Единственно правильный
ответ: последовательность случайных чисел _ это последователь-
ность, в которой все элементы являются несвязанными. Это опреде-
ление приводит к такому парадоксу, что любая последовательность
может быть как случайной, так и неслучайной в зависимости от то-
го, как эта последовательность получена. Например, следующая
строка чисел
1 2 3 4 5 6 7 8 9 0
была получена печатанием верхней строки клавиатуры по порядку,
таким образом последовательность конечно не может рассматриваться
как сгенерированная случайным образом. Но как быть, если вы полу-
чите ту же самую последовательность, вынимая пронумерованный тен-
нисные шары из боченка. В данном случае это уже случайным образом
сгенерированная последовательность. Данный пример показывает, что
случайность последовательности зависит от того, как она была по-
лучена, а не от нее самой.
Помните, что последовательность чисел, сгенерированная
компьютером, является детерминированной: каждое число, кроме пер-
вого, зависит от предшествующих чисел. Технически это означает,
что компьютером может быть сгенерирована только квазислучайная
последовательность чисел. Однако, этого достаточно для большинс-
тва задач и в данной книге такие последовательности для простоты
будут называться случайными.
В общем случае считается хорошо, когда числа в последова-
тельности случайных чисел распределены равномерно (не путайте это
с нормальным распределением или колоколообразной кривой). При
равномерном распределении все события равновероятны так, что ди-
аграмма равномерного распределения стремится к прямой горизон-
тальной линии, а не к кривой.
До широкого распространения компьютеров всякий раз, когда
необходимы были случайные числа, они получались либо бросанием
игральных костей, либо выниманием пронумерованных шаров из ящика.
В 1955 году фирма RAND опубликовала таблицу из 1 миллиона случай-
ных чисел, полученных с помощью вычислительной машины. На ранней
стадии развития вычислительной техники было разработано много ме-
тодов генерации случайных чисел, но большинство из них не нашло
применения.
Один очень интересный метод был разработан Джоном фон Нейма-
ном; его часто называют среднеквадратичным. В данном методе пре-
дыдущее случайное число возводится в квадрат, а затем из резуль-
тата выделяются средние цифры. Например, если вы создаете числа
из трех цифр, а предыдущее число было 121, то возведение в квад-
рат дает результат 14641. Выделение трех средних цифр дает следу-
ющее случайное число 464. Недостатком данного метода является то,
что он имеет очень короткий период повторения, называемый циклом.
По данной причине данный метод сегодня не используется.
В настоящий момент наиболее часто применяется метод генера-
ции случайных чисел, основывающийся на использовании уравнения
R = (aR +c)modm
n+1 n
при выполнении следующих условий
R>0
a>0
c>0
m>R , a и c
Отметим, что R - это предыдущее число, а R - следующее. Дан-
ный метод иногда называют линейным сравнительным методом. Формула
так проста, что вы можете подумать, что генерировать случайные
числа просто. Однако, это ловушка: насколько хорошо работает дан-
ная формула, очень сильно зависит от значения а, с и m. Выбор
значений иногда в большей степени искусство, нежели наука. Су-
ществуют сложные правила, которые могут помочь вам выбрать значе-
ния; однако, мы рассмотрим лишь несколько простых правил и приме-
ров.
Модуль (m) должен быть довольно большим, так как он опреде-
ляет область случайных чисел. Операция взятия по модулю порождает
остаток от деления числа на модуль. Следовательно, 10 по модулю 4
равно 2. Таким образом, если модуль равен 12, то формулой порож-
даются числа от 0 до 11, а если модуль равен 21425, то порождают-
ся числа от 0 до 21424. Выбор множителя а и приращения с является
очень сложной задачей. В общем случае множитель может быть до-
вольно большим, а приращение - маленьким. Множество попыток и
проверок необходимо, чтобы создать хороший генератор.
В качестве первого примера здесь приведен один из наиболее
часто используемых генераторов случайных чисел. Уравнение, пока-
занное в Rаn1 используется как основа для генератора случайных
чисел в ряде популярных языков.
var
a1: integer; { установка до первого вызова Ran1 }
function Ran1: real;
var
t: real;
begin
t := (a1*32749+3) mod 32749;
a1 := Trunc(t);
Ran1 := Abs(t/32749);
end; {Rea1}
Данная функция имеет три главные особенности. Во-первых,
случайные числа в действительности являются целыми, хотя функция
возвращает действительные числа. Данный метод работает с целыми
числами, но генераторы случайных чисел, как это принято, должны
возвращать числа в пределах от 0 до 1, что означает, что это
должны быть числа с плавающей запятой.
Во-вторых, начальное значение задается через глобальную пе-
ременную а1. До первого вызова Ran1 переменная а1 должна быть ус-
тановлена в 1.
В-третьих, в Ran1 случайные числа делятся на модуль прежде,
чем они будут возвращены функцией, для того, чтобы числа лежали в
области от 0 до 1. Если вы поинтересуетесь значением глобальной
переменной а1 до возврата строки, то оно должно лежать в области
от 0 до 32748. Следовательно, когда а1 делится на 32749, получен-
ное число будет больше или равно 0 и меньше 1.
Многие генераторы случайных чисел не применимы, так как они
порождают не равномерное распределение или имеют короткий цикл
повторения. Даже когда эти недостатки не очень бросаются в глаза,
они могут породить смешанный результат, если такой генератор ис-
пользуется снова и снова. Решение заключается в том, чтобы соз-
дать различные генераторы и применять их индивидуально или сов-
местно для получения более качественных последовательностей
случайных чисел. Применение нескольких генераторов может сгладить
распределение последовательности за счет уменьшения малых смеше-
ний отдельных генераторов. Далее приведена функция генерирования
случайных чисел, называемая Ran2, которая порождает хорошее расп-
ределение:
var
a2:integer; { установить в значение 203 до первого вызова
Ran2 }
function Ran2: real;
var
t: real;
begin
t := (a2*10001+3) mod 17417;
a2 := Trunc(t);
Ran2 := Abc(t/17417);
end; {Ran2}
Оба этих генератора случайных чисел порождают хорошие после-
довательности случайных чисел. Тем не менее остаются вопросы:
достаточно ли "случайной" является последовательность? Хороши ли
данные генераторы?
|