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

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

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

История генераторов случайных чисел уходит корнями к одному из самых известных имен в теории вычислительных машин - Джону фон Нейману (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-битных чисел. В общем случае, несмотря простоту, применение метода средних квадратов вследствие его недостатков предельно ограничено.

Оглавление книги