Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл

Полученное нами значение параметра X попадает в диапазон от 5% до 95%, т.е. на его основе мы не можем прийти к четкому заключению о смещенном центре тяжести монет. Приходится предполагать, что монеты являются настоящими (без всяких "хитростей"). Если же, с другой стороны, значение X было равно 10, можно было бы сказать, что такая ситуация может складываться не более чем в 1% экспериментов (10 больше чем 9.21 - значения для столбца 99%). Это послужило бы веским доказательством того, что монеты имеют смещенный центр тяжести. Конечно, потребуется провести большее количество экспериментов, и посмотреть, каким образом получаемые данные соотносятся со стандартным распределением хи-квадрат. По такому расширенному набору данных можно будет более точно оценить случайность получаемых данных. Не хотелось бы делать выводы, основываясь на результатах, которые согласно теории вероятностей, хотя и редко, но все же могут быть получены.

Как правило, при оценке случайного характера получаемых результатов берется одна и та же граница с каждого конца распределения хи-квадрат, скажем, 5% и 95%, и утверждается, что эксперимент является достоверным на уровне 5%, если данные эксперимента не попадают в эти границы, и недостоверным на уровне 5% - в противном случае.

До сих пор мы не упоминали еще один аспект: какое количество отдельных событий нужно генерировать? В нашем примере с монетами их было 100. Достаточно ли такого количества? Или можно обойтись и меньшим объемом экспериментов? Или же количество событий должно быть больше? К сожалению, четкого ответа на поставленные вопросы не существует. Кнут (Knuth) утверждает, что хорошим практическим методом для определения достаточности объема экспериментов является следующее: количество ожидаемых событий каждого типа должно быть не менее пяти (в нашем случае ожидаемыми значениями являются 25, 50 и 25, следовательно, объем нашего эксперимента вполне достаточен для оценки случайности результатов), но чем больше событий каждого типа, тем лучше [11].

Давайте оставим наши монеты в покое и вернемся к гипотетической последовательности случайных чисел. Воспользуемся всеми только что полученными знаниями. Определим количество вхождений каждого числа, вычислим значение параметра X и посмотрим, как оно соответствует распределению хи-квадрат с девятью степенями свободы (для последовательности однозначных чисел возможно выпадение одного из 10 чисел;

таком образом, количество степеней свободы будет на единицу меньше, т.е. 9). Минимальный объем экспериментов должен составлять, по крайней мере, 50 чисел (чтобы количество разных чисел было не менее 5), хотя чем длиннее последовательность, тем лучше.

Можно пойти даже дальше. Если рассматривать последовательность как серию пар чисел от 00 до 99, считая каждую пару отдельным событием, ее можно будет разбить на 100 типов событий. Следовательно, количество степеней свободы будет равно 99. Вероятность выпадения каждой пары составляет 1:100. Таким образом, для обеспечения возможности оценки случайности последовательности она должна содержать не менее 500 пар (1000 чисел).

Более того, можно использовать не пары чисел, а тройки, но в этом случае понадобится проводить еще больший объем экспериментов. Существуют и другие виды тестов, но перед их рассмотрением давайте выясним, как можно генерировать случайные числа. После изучения нескольких генераторов последовательностей случайных чисел можно будет прогнать тесты на результатах их работы.

Еще раз хотелось бы повторить, что детерминированные алгоритмы не могут генерировать последовательности случайных чисел, аналогичные получаемым при бросках игрального кубика или при подсчете количества бета-частиц во время распада радиоактивного материала. Детерминированные алгоритмы на основе одинаковых исходных данных будут генерировать одни и те же последовательности чисел. Если, например, генератор X, основанный на четко определенном алгоритме, для начального числа 12 345 678 генерирует случайное число 65 584 256, то даже через пять месяцев тот же генератор X при том же начальном числе даст значение 65 584 256. Следовательно, в вычислении последовательности случайных чисел нет случайности, но с помощью статистических тестов можно показать, что последовательность чисел, генерируемая подобным образом, содержит случайные числа.

Более того, в некоторых случаях повторяемость последовательности случайных чисел бывает даже желательна. Она позволяет использовать генератор для многократного воспроизведения одной и той же последовательности. Такая возможность бывает необходимой в процессе отладки с целью воспроизведения ошибки.

Метод средних квадратов

История генераторов случайных чисел уходит корнями к одному из самых известных имен в теории вычислительных машин - Джону фон Нейману (John von Neumann). В 1946 году он предложил следующую схему генерации последовательностей случайных чисел: возьмите N-значное число, возведите его в квадрат и из результата, выраженного в виде 2N-значного числа (при необходимости дополненного слева до 2N-значного), возьмите средние N цифр. Это и будет следующее число в последовательности. Так, например, если N равно 4, в качестве начального числа можно взять 1234. Следующими числами в последовательности будут 5227, 3215, 3362, 3030, 1809 и т.д. Описанный метод известен под названием метода средних квадратов (middle-square method).

Листинг 6.1. Метод средних квадратов в действии

var

MidSqSeed : integer;

function GetMidSquareNumber : integer;

var

Seed : longint;

begin

Seed := longint(MidSqSeed) * MidSqSeed;

MidSqSeed := (Seed div 100) mod 10000;

Result := MidSqSeed;

end;

К сожалению, с приведенным алгоритмом связано несколько больших проблем, которые исключают его применение в практических целях. Вернемся к нашему примеру с четырехзначными случайными числами. Предположим, что в последовательности нам встретилось число меньше 10. При вычислении квадрата будет получено число меньше 100. Это, в свою очередь, означает, что следующим числом в последовательности будет 0 (поскольку мы возьмем четыре средние цифры из числа 000000хх). Это число также меньше 10, следовательно, все последующие числа в последовательности будут равны 0. Вряд ли кто-то может сказать, что такая последовательность будет случайной! (Если в качестве начального взять число 1234, то до попадания в 0 последовательность будет содержать 55 чисел.) Кроме того, если начать, например, с числа 4100, последовательность будет состоять из 8100, 6100, 2100, 4100 и так до бесконечности. Существуют и другие патологические последовательности, на которые очень легко натолкнуться и очень трудно избежать.

Метод средних квадратов позволяет легко генерировать случайные числа на основе 16-битного целого числа. Возведение 16-битного числа в квадрат дает 32-битное число. Затем для вычисления средних 16-бит нужно всего лишь сдвинуть полученный результат на 8 бит вправо и выполнить операцию AND с числом $FFFF. Тем не менее, даже в этом случае алгоритм средних квадратов будет давать бесполезные результаты. После 50-60 случайных чисел алгоритм приводит к генерации нулей или попадает в цикл. То же самое происходит и для 32-битных чисел. В общем случае, несмотря простоту, применение метода средних квадратов вследствие его недостатков предельно ограничено.

Линейный конгруэнтный метод

Следующий большой шаг в разработке генераторов случайных чисел был сделан Д. Лемером (D.H. Lehmer) в 1949 году. Предложенный им генератор носит название линейного конгруэнтного метода (linear congruential method). Выберите три числа m, a и c и начальное число Х(_0_). Для генерации последовательности случайных чисел используется следующая формула:

Х(_n+1_) = (аХ(_n_) + с) mod m

Операция взятия по модулю m (mod m) представляет собой вычисление остатка от деления числа на m, например, 24 mod 10 = 4.

При удачном выборе начальных чисел генерируемая последовательность будет содержать случайные числа. Например, стандартный генератор случайных чисел в Delphi использует значения a = 134775813 ($8088405), c = 1 и m = 2(^32^), а значение Х(_0_) выбирается самим пользователем. (Значение начального числа содержится в глобальной переменной RandSeed. Его можно задавать напрямую или использовать процедуру Randomize для вычисления его на основе показаний системных часов.)

Следует отметить, что если в двух разных точках последовательности получено одно и то же значение x, то последовательность в этих двух точках должна полностью повторяться, поскольку алгоритм детерминированный. Так как в формуле используется операция определения остатка от деления, все значения в последовательности будут меньше m, т.е. будут находиться в диапазоне от 0 до m-1. Следовательно, последовательность будет повторяться после не более чем m чисел. При неудачном выборе значения a, c и m повторение последовательности может начаться гораздо раньше. В качестве простого примера можно привести случай, когда a = 0: вся последовательность сводится к повторению значения параметра c - {c, c, c, . . .}