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

Метод средних квадратов позволяет легко генерировать случайные числа на основе 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, . . .}

Каким образом можно выбрать удачные значения для a, c и m? В литературе содержится немало размышлений, описаний и доказательств. Как правило, значение параметра m выбирается как можно больше, чтобы цикл повторяемости был также как можно большим. Нужно выбирать его, как минимум, равным размеру слова операционной системы (другими словами, для 32-разрядных операционных систем m выбирается равным 31 или 32 бита). Значение параметра а выбирается таким образом, чтобы оно было взаимно простым со значением числа m (два числа являются взаимно простыми, если их наибольший общий делитель равен 1). Значение c, как правило, берется равным 0 или 1, несмотря на то, что общее правило гласит, что должно выбираться ненулевое значение, взаимно простое со значением параметра m.

В случае если значение с равно 0, генератор называется мультипликативным линейным конгруэнтным генератором случайных чисел (multiplicative linear congruential generator). Чтобы гарантировать, что цикл повторения последовательности максимален, необходимо в качестве значения параметра m выбирать простое число. Самым известным генератором подобного рода является так называемый минимальный стандартный генератор случайных чисел (minimal standard random number generator), предложенный Стивеном Парком (Stephen Park) и Кейтом Миллером (Keith Miller) в 1988 году. Для него а = 16807, а m = 2147483647 (или 2(^31^) - 1). После разработки этого генератора было проведено большое количество статистических тестов, и генератор прошел большинство из них (несмотря на то что предложенный генератор обладает определенными нежелательными свойствами, которые мы рассмотрим чуть ниже).

Мультипликативные линейные конгруэнтные генераторы случайных чисел имеют одну аномалию: они никогда не дают числа 0. (Это объясняется тем, что, во-первых, m представляет собой простое число, во-вторых, a mod m не равно нулю, и, в-третьих, если начальное число не равно нулю, Х(_0_) mod m тоже не равно нулю.) Следовательно, если генераторы никогда не дают числа 0, их нельзя назвать случайными. На практике невозможность генерации нуля, как правило, игнорируется, - в конце концов, в 32-разрядной операционной системе это всего лишь отсутствие всего одного числа из примерно 2 миллиардов.