|
БЕСПОВТОРНЫЕ СЛУЧАЙНЫЕ ЧИСЛАВ случае, когда необходимы бесповторные случайные числа, можно воспользоваться принципами создания автономной линейной последовательностной машины (АЛПМ) или покоящейся линейной последовательностной машины (ПЛПМ), которые способны генерировать 2 n –1 различных двоичных чисел, где n – разрядность машины. АЛПМ (рис. 1) представляет собой регистр сдвига с обратной связью, формируемой элементом М2. Элементы bi фиктивны – они имитируют наличие связи выхода i –го разряда регистра с элементом М2 (bi = 1) или ее отсутствие (bi = 0). Максимальный период 2 n –1 повторения чисел получается только при определенных значениях bi, которые образуются из коэффициентов многочленов максимального показателя , приведенным в [4 (табл. 5)]. Правило их определения сводится к следующему. Если представить в виде , где , то bi можно найти из выражения Таким образом получаем . Индексы коэффициентов bi, равных 1 и позволяющих построить АЛПМ максимального периода, для некоторых n даны в табл. 1. Таблица 1 Индексы единичных коэффициентов bi, порождающих АЛПМ максимального периода 2 n –1
В [4 (табл. 5)] даны коэффициенты полиномов максимального показателя для , 107, 127. АЛПМ максимального периода генерирует псевдослучайные целые числа от 1 до 2 n –1, причем первое число определяется ее начальным состоянием X0 (состоянием разрядов ее регистра сдвига в начальный момент времени). ПЛПМ максимального периода получается из АЛПМ добавлением одного входа схемы М2, на который подается логическая единица. Такая ПЛПМ способна генерировать целые числа от 0 до 2 n –2. Поскольку все числа различны, то мы имеем равномерное распределение на интервале (1, 2n – 1) или (0, 2n-2). Если рассматривать числа на интервале меньше предельного, то равномерность может нарушиться. Практика показывает, что это нарушение незначительно. Для получения чисел в интервале (0,1) достаточно разделить числа, получаемые АЛПМ или ПЛПМ, на период 2 n –1. При этом для АЛПМ получим числа в интервале , а для ПЛПМ в интервале . Если необходимы и 0, и 1, то для АЛПМ надо искусственно получить 0 либо в начале последовательности, либо в ее конце, а для ПЛПМ так надо поступить с 1. Смоделировать работу АЛПМ или ПЛПМ программным способом можно двояко: либо на битовом уровне, производя сдвиг слова (слов) и выделяя его (их) разряды для формирования обратной связи, либо представив регистр в виде одномерного массива, элементы которого соответствуют его разрядам, и производя все необходимые действия с элементами этого массива. ОЦЕНКА КАЧЕСТВА ГЕНЕРИРУЕМОЙ ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ЧИСЕЛ КРИТЕРИИ ОЦЕНКИ КАЧЕСТВА Поскольку генерирование случайных чисел базируется на равномерном распределении, то в первую очередь важно оценить качество генерирования случайных равномерно распределенных чисел в интервале (0,1). Выбирая различные значения a, b, М и в формулах (4) и (5), можно получить последовательности чисел лучше или хуже приближающихся к случайной последовательности чисел, распределенной равномерно. Оценку качества приближения обычно производят по известным в статистике критериям: · Близости математического ожидания и дисперсии теоретического и полученного распределения; · Близости теоретического и полученного распределения в целом, оцениваемой по критерию . Наличие или отсутствие начального неслучайного участка можно определить на основе анализа нормированной автокорреляционной функции, описывающей взаимосвязь элементов статистической последовательности, так как для случайной последовательности эта функция близка к нулю. Первые две проверки имеют смысл только для случайных совокупностей без начального неслучайного участка, поэтому проверку качества сгенерированной последовательности целесообразно начать с анализа нормированной автокорреляционной функции. ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры... Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|