БЕСПОВТОРНЫЕ СЛУЧАЙНЫЕ ЧИСЛА

В случае, когда необходимы бесповторные случайные числа, можно воспользоваться принципами создания автономной линейной последовательностной машины (АЛПМ) или покоящейся линейной последовательностной машины (ПЛПМ), которые способны генерировать 2ⁿ–1 различных двоичных чисел, где n – разрядность машины.

АЛПМ (рис. 1) представляет собой регистр сдвига с обратной связью, формируемой элементом М2. Элементы b_i фиктивны – они имитируют наличие связи выхода i–го разряда регистра с элементом М2 (b_i = 1) или ее отсутствие (b_i = 0). Максимальный период 2ⁿ–1 повторения чисел получается только при определенных значениях b_i, которые образуются из коэффициентов многочленов максимального показателя , приведенным в [4 (табл. 5)].

Правило их определения сводится к следующему.

Если представить в виде

,

где , то b_i можно найти из выражения

Таким образом получаем

.

Индексы коэффициентов b_i, равных 1 и позволяющих построить АЛПМ максимального периода, для некоторых n даны в табл. 1.

Таблица 1

Индексы единичных коэффициентов b_i,

порождающих АЛПМ максимального периода 2ⁿ–1

В [4 (табл. 5)] даны коэффициенты полиномов максимального показателя для , 107, 127.

АЛПМ максимального периода генерирует псевдослучайные целые числа от 1 до 2ⁿ–1, причем первое число определяется ее начальным состоянием X₀ (состоянием разрядов ее регистра сдвига в начальный момент времени).

ПЛПМ максимального периода получается из АЛПМ добавлением одного входа схемы М2, на который подается логическая единица. Такая ПЛПМ способна генерировать целые числа от 0 до 2ⁿ–2.

Поскольку все числа различны, то мы имеем равномерное распределение на интервале (1, 2ⁿ – 1) или (0, 2ⁿ-2). Если рассматривать числа на интервале меньше предельного, то равномерность может нарушиться. Практика показывает, что это нарушение незначительно.

Для получения чисел в интервале (0,1) достаточно разделить числа, получаемые АЛПМ или ПЛПМ, на период 2ⁿ–1. При этом для АЛПМ получим числа в интервале , а для ПЛПМ в интервале .

Если необходимы и 0, и 1, то для АЛПМ надо искусственно получить 0 либо в начале последовательности, либо в ее конце, а для ПЛПМ так надо поступить с 1.

Смоделировать работу АЛПМ или ПЛПМ программным способом можно двояко: либо на битовом уровне, производя сдвиг слова (слов) и выделяя его (их) разряды для формирования обратной связи, либо представив регистр в виде одномерного массива, элементы которого соответствуют его разрядам, и производя все необходимые действия с элементами этого массива.