Линейный конгруэнтный метод

Содержание

Введение

1. Генератор псевдослучайных чисел

2. Методы получение псевдослучайных чисел

Линейный конгруэнтный метод

Метод Фибоначчи

Вихрь Мерсенна

3. Тестирование псевдослучайных последовательностей

4. Генератор случайных чисел в Borland C++

Заключение

5. Список использованных источников

Приложение

Введение

 

Программа предназначена для формирования и просмотра команды для олимпиады по программированию.

а) Ввод информации.

По запросу с клавиатуры поочередно вводятся фамилия, имя студента, а также язык программирования, на котором он предпочитает писать программы (Pascal, C,C++).

б) Просмотр введенного списка.

Если список не пустой, то при выборе этого пункта меню на экран поочередно выводится полная информация о каждом студенте.

в) Отбор команды.

При выборе этого пункта меню пользователь должен указать язык программирования, на основании этого из списка студентов выбирается не более трех человек (их может быть меньше), владеющих этим языком.

г) Проверка, может ли быть укомплектована команда.

Предполагается, что команда состоит из трех человек. Пользователь вводит язык программирования, а программа сообщает ему, можно ли или нельзя укомплектовать команду (можно, если студентов, владеющих данным языком, не менее трех)

Реализовать программу на базе связного списка.

генератор псевдослучайное число последовательность

Генератор псевдослучайных чисел

 

Физическое моделирование случайности с помощью таких физических явлений как, например, радиоактивное излучение или дробовой шум в электронной лампе является довольно сложным и дорогостоящим, а использование нажатия клавиш и движение мыши требует усилий пользователя и к тому же не дают полностью настоящих случайных процессов. Поэтому вместо физического моделирования используют методы математического моделирования случайности и генерации случайных последовательностей в виде программ для ЭВМ или специализированных устройств.

Эти программы и устройства хотя и называются генераторами случайных чисел, на самом деле генерируют детерминированные последовательности, которые только кажутся случайными по своим свойствам и поэтому называются псевдослучайными последовательностями.

Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) - алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Самая важная характеристика генератора псевдослучайных чисел - это информационная длина его периода, после которого числа будут либо просто повторяться, либо их можно будет предсказать.

Любые программные ГПСЧ, не использующие внешних "источников энтропии" и формирующие очередное число только алгебраическими преобразованиями, не дают чисто случайных чисел. Последовательность на выходе такого генератора выглядит как случайная, но на самом деле подчиняется некоторому закону и, как правило, рано или поздно зацикливается. Такие числа называются псевдослучайными. Рассмотрим теперь некоторые практические методы получения псевдослучайных чисел.

Методы получение псевдослучайных чисел

 

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

Линейный конгруэнтный метод

Линейный конгруэнтный метод - один из алгоритмов генерации псевдослучайных чисел. Входит в стандартные библиотеки различных компиляторов.

Этот алгоритм заключается в итеративном применении следующей формулы:

 

,

 

где a>0, c>0, m>0 - некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства этой последовательности определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда:

) НОД (c, m) = 1 (то есть c и m взаимно просты)

) a - 1 кратно p для всех простых p - делителей m;

) a - 1 кратно 4, если m кратно 4.

Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором коэффициентов a и c.

Метод Фибоначчи

Интересный класс генераторов псевдослучайных последовательностей основан на использовании последовательностей Фибоначчи. Классический пример такой последовательности {0,1,1,2,3,5,8,13,21,34 …} - за исключением первых двух ее членов, каждый последующий член равен сумме двух предыдущих.

Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делают невозможным их использование в статистических алгоритмах, требующих высокого разрешения.

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность, и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел. В англоязычной литературе фибоначчиевы датчики такого типа называют обычно "Subtract-with-borrow Generators" (SWBG).

Наибольшую популярность фибоначчиевы датчики получили в связи с тем, что скорость выполнения арифметических операций с вещественными числами сравнялась со скоростью целочисленной арифметики, а фибоначчиевы датчики естественно реализуются в вещественной арифметике.

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:

 

=

 

где - вещественные числа из диапазона [0,1), a,b - целые положительные числа, называемые лагами. Для работы фибоначчиеву датчику требуется знать max{a,b} предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется max{a,b} случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.

Лаги a и b - "магические" и их не следует выбирать произвольно. Рекомендуются следующие значения лагов: (a, b) = (55,24), (17,5) или (97,33). Качество получаемых случайных чисел зависит от значения константы, a чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.

Значения (a,b) = (17,5) можно рекомендовать для простых приложений, не использующих векторы высокой размерности со случайными компонентами. Значения (a,b) = (55,24) позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения (a,b) = (97,33) позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности. Получаемые случайные числа обладают хорошими статистическими свойствами, причём все биты случайного числа равнозначны по статистическим свойствам.

Вихрь Мерсенна

Вихрь Мерсенна (Mersenne twister) - это генератор псевдослучайных чисел, основанный на свойствах простых чисел Мерсенна и обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Вихрь Мерсенна лишен многих недостатков присущих другим ГПСЧ таких как малый период, предсказуемость, легко выявляемая статистическая зависимость.

Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (twisted generalised feedback shift register, TGFSR). "Вихрь" - это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5-ю измерениями). Поэтому корреляция между последовательными значениями в выходной последовательности Вихря Мерсенна пренебрежимо мала.

Вихрь Мерсенна имеет огромный период, а именно, доказано, что его период равен числу Мерсенна 219937−1, что более чем достаточно для многих практических приложений.

Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2-3 раза быстрее линейных конгруэнтных генераторов). Алгоритм основан на следующем рекуррентном выражении:

 

= + ( ) A, (k=0,1,2…)

 

где n - целое, которое обозначает степень рекуррентности,- целое, 1< m < n,

А - матрица размера WxW

В правой части обозначает "старшие w-r бит" , и , "младшие r бит"