Метод перемешивания

Метод серединных произведений

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

Имеется некоторое четырехзначное число R0. Это число возводится в квадрат и заносится в R1. Далее из R1 берется середина (четыре средних цифры) — новое случайное число — и записывается в R0. Затем процедура повторяется (см. рис. 22.6). Отметим, что на самом деле в качестве случайного числа необходимо брать не ghij, а 0.ghij — с приписанным слева нулем и десятичной точкой. Этот факт отражен как на рис. 22.6, так и на последующих подобных рисунках.

Рис. 22.6. Схема метода серединных квадратов

Недостатки метода: 1) если на некоторой итерации число R0 станет равным нулю, то генератор вырождается, поэтому важен правильный выбор начального значения R0; 2) генератор будет повторять последовательность через Mⁿ шагов (в лучшем случае), где n — разрядность числа R0, M — основание системы счисления.

Для примера на рис. 22.6: если число R0 будет представлено в двоичной системе счисления, то последовательность псевдослучайных чисел повторится через 2⁴ = 16 шагов. Заметим, что повторение последовательности может произойти и раньше, если начальное число будет выбрано неудачно.

Описанный выше способ был предложен Джоном фон Нейманом и относится к 1946 году. Поскольку этот способ оказался ненадежным, от него очень быстро отказались.

Число R0 умножается на R1, из полученного результата R2 извлекается середина R2^* (это очередное случайное число) и умножается на R1. По этой схеме вычисляются все последующие случайные числа (см. рис. 22.7).

Рис. 22.7. Схема метода серединных произведений

В методе перемешивания используются операции циклического сдвига содержимого ячейки влево и вправо. Идея метода состоит в следующем. Пусть в ячейке хранится начальное число R0. Циклически сдвигая содержимое ячейки влево на 1/4 длины ячейки, получаем новое число R0^*. Точно так же, циклически сдвигая содержимое ячейки R0 вправо на 1/4 длины ячейки, получаем второе число R0^**. Сумма чисел R0^* и R0^** дает новое случайное число R1. Далее R1 заносится в R0, и вся последовательность операций повторяется (см. рис. 22.8).

Рис. 22.8. Схема метода перемешивания

Обратите внимание, что число, полученное в результате суммирования R0^* и R0^**, может не уместиться полностью в ячейке R1. В этом случае от полученного числа должны быть отброшены лишние разряды. Поясним это для рис. 22.8, где все ячейки представлены восемью двоичными разрядами. Пусть R0^* = 10010001₂ = 145₁₀, R0^** = 10100001₂ = 161₁₀, тогда R0^* + R0^** = 100110010₂ = 306₁₀. Как видим, число 306 занимает 9 разрядов (в двоичной системе счисления), а ячейка R1 (как и R0) может вместить в себя максимум 8 разрядов. Поэтому перед занесением значения в R1 необходимо убрать один «лишний», крайний левый бит из числа 306, в результате чего в R1 пойдет уже не 306, а 00110010₂ = 50₁₀. Также заметим, что в таких языках, как Паскаль, «урезание» лишних битов при переполнении ячейки производится автоматически в соответствии с заданным типом переменной.