35025

Датчики случайных чисел

Лабораторная работа

Информатика, кибернетика и программирование

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

Русский

2014-03-24

811.54 KB

21 чел.

Лабораторная работа №3

Датчики случайных чисел.

Цель работы.

Изучение датчиков случайных чисел, математическая реализация простого датчика случайных чисел в MathCad.

Теоретическая часть.

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

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

  1. квадратов;
  2. произведений;
  3. мультипликативный конгруэнтный;
  4. смешанный конгруэнтный.

Метод квадратов. В квадрат возведено текущее случайное число и из результатов средних разрядов выделяется следующее число.
Метод произведений. Два следующих друг за другом случайных числа умножают а из произведения средних разрядов выделяют следующее случайное число.
Мультипликативный конгруэнтный метод. В качестве текущего значения случайного числа выделяют остаток от деления произведения предыдущего случайного числа и постоянного множителя a на постоянное число m:

yi=a*yi-1*(mod m),

где a, m -постоянные числа; yi - случайное число.
Смешанный конгруэнтный метод. Этот метод отличается от предыдущего прибавлением к остатку от деления постоянного числа m:

yi=a*yi-1+m*(mod m),

Перечисленные методы также обладают своими недостатками, поэтому датчики случайных чисел, реализованные на их основе проверяют. Различают три типа проверки: 

  1. на периодичность;
  2. на случайность;
  3. на равномерность.

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

При проверке на случайность используют совокупность тестов проверки: частот; пар; комбинаций; серий; корреляции.   
В первых четырех тестах осуществляется разбиение диапазона распределения на t интервалов и выполняется подсчет количества попаданий случайных чисел в выделенные интервалы. Полученное эмпирическое распределение сравнивается с теоретическим. Для сравнения используются критерии согласия Колмогорова и c2.

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

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

Так называемый мультипликативный конгруэнтный датчик задается двумя параметрами: модулем m и множителем k. Обычно это достаточно большие целые числа.

При заданных m, k числа z1, z2, ..., вычиcляются по рекуррентной формуле:

Ai = (kAi -1) mod m, i = 1, 2,...,                     

zi = Ai / m,

где m - модуль, k - множитель, A0 - начальное значение, mod - операция вычисления остатка от деления kAi -1 на m.

Таким образом, A1 определяется как остаток от деления  kA0 на m; A2 - как остаток от деления kA1 на m и т.д. Поскольку все числа Ai - это остатки от деления на m, то 0 Ј  Ai < m. Разделив последнее неравенство на m, видим, что 0 Ј Ai / m< 1, т. е. 0 Ј zi <1.

Из неравенства 0 Ј Ai < m вытекает также, что датчик дает периодическую последовательность Ai. Действительно, число всех возможных остатков от 0 до m - 1 равно m и, рано или поздно, на каком-то шаге i обязательно появится значение Ai, уже встречавшееся ранее. С этого момента последовательность Ai “зациклится".

Длина периода T будет не больше m - 1. Например, если встретится остаток Ai= 0, то далее, согласно рекуррентной формуле , будет Ai+ 1 = 0, Ai+ 2 = 0, ... , т.е. длина периода T = 1. Ненулевых же остатков в интервале 0Ј Ai < m всего m - 1, и, если все они войдут в период, будет T = m - 1. Это имеет место, например, при m = 13, k = 7; в этом случае ряд Ai выглядит так:

                        1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2,            1, 7,... .
\_________________________/

            T = m - 1 = 12

Поскольку в качестве случайной можно использовать лишь подпоследовательность Ai внутри одного периода, то параметры датчика выбирают так, чтобы длина периода T была максимальной. С учетом ограничения TЈ m - 1 модуль m берут максимально возможным. Чтобы упростить вычисление остатков по (2.5), для двоичных ЭВМ часто берут m = 2n. Рекомендуется также брать достаточно большой множитель k, причем взаимно простой с m.

В [30] можно найти подробные рекомендации по выбору параметров m, k и начального значения A0 . Заметим, однако, что в настоящее время не известны правила, которые гарантировали бы высокое качество датчика без его специального статистического тестирования.

Датчик называют мультипликативно-конгруэнтным потому, что он использует две основные операции - умножение (англ. multiplication) и вычисление остатка (в теории чисел - получение конгруэнтного числа). Можно было бы поэтому перевести его название и как "множительно-остатковый датчик".

Обратим внимание также и на то, что операция вычисления остатка воплощает здесь неймановский принцип вытаскивания цифр. Это становится очевидным, если записывать числа в системе счисления с основанием m. Тогда операция X mod m означает выбор последней цифры из числа X. Для m = 2n операция X mod m означает также выделение последних n цифр из двоичной записи числа X.

Функцию выполняющую роль датчика случайных чисел в системе MathCad, является функция rnd(x), где х максимальное значение случайного числа. Для получения характеристик гаммы так же понадобятся функции: mean(x), max(x), stdev(x), var(x), min(x).

Для наглядной иллюстрации равномерности распределения, а так же гистограммы распределения необходимо применить графический аппарат MathCad.

В математической системе MathCad есть возможность построение 2х и 3х мерных графиков.

Рис.1 Общий вид графика функции

Рис.2 меню форматирования графика

Рис.3 меню управления графиками функций

Задание для лабораторной  работы.

1)Используя датчик случайных чисел системы MathCad, получить последовательность из 1000 чисел, в диапазоне от 0 до 10, и построить гистограмму распределения случайных чисел, при помощи встроенной функции hist(int,x).

2)Реализовать мультипликативный конгруэнтный датчик, выдающий последовательность из 1000 случайных чисел, по заданному числу А, и фиксированных m=2^36, k=5^15, при условии, что случайные числа должны находится в диапазоне от 0 до 10.

Порядок выполнения работ.

1-ое задание

  1. Согласно заданию необходимо задать диапазон последовательности от 0 до 1000.
  2. При помощи функции “rnd” задаем диапазон от  0 до 10.
  3. Вывести последовательность из 1000 чисел.

  1. Задать диапазон от 0 до 10 и присвоить его значению intj.
  2. Присваиваем переменной (например f) функцию hist(int,y)
  3. Строим гистограмму распределения случайных чисел.

2-ое задание

  1. Задать согласно заданию на лабораторную работу модуль - m, множитель - k, начальное значение – A0 (любое число от 1 до 20).
  2. Согласно заданию необходимо задать диапазон последовательности от 1 до 1000.
  3. Записать рекуррентную формулу (Ai, zi).
  4. Вывести zi последовательность из 1000 чисел.

  1. Вывести zi последовательность из 1000 чисел в виде графика.

  1. Задать диапазон от 0 до 10 и присвоить его значению intj.
  2. Присваиваем переменной (например f) функцию hist(int,x)
  3. Строим гистограмму распределения случайных чисел.

Контрольные вопросы.

  1. Где применяются датчики случайных чисел?
  2. Четыре методы генерирования случайных чисел?
  3. Построение декартова графика в системе MathCad, форматирование графика, реализация нескольких графиков функций от одного аргумента на одном графике?
  4. Три типа проверки с генерированных датчиков случайных чисел?
  5. Реализация мультипликативного конгруэнтного метода?

Содержание отчета.

1.Отчет должен быть выполнен на бумаге формата А4.

2.Отчет должен содержать  краткую теорию по теме работы.

3.Отчет должен содержать текст программ MathCad с комментариями.

4.Отчет должен содержать выводы о проделанной лабораторной работе.


 

А также другие работы, которые могут Вас заинтересовать

78266. Гнойно-воспалительные заболевания у детей 164 KB
  В этих случаях с момента рождения у ребенка могут выявляться такие заболевания как везикулопустулез пузырчатка внутриутробная пневмония менингит сепсис и др. Однако основным путем является инфицирование ребенка после рождения. При необильном высыпании общее состояние ребенка не нарушено аппетит сохранен температура тела нормальная и реже субфебрильная а при обильном высыпании появляются симптомы интоксикации. Пузырчатка новорожденного Она развивается чаще в первые 2 недели жизни ребенка.
78267. Острые пневмонии у детей 135 KB
  Некоторые из них в том числе острые пневмонии являются одной из причин смертности детей в раннем возрасте хотя от пневмоний дети не должны умирать. Дети в этом возрасте длительное время находятся в горизонтальном положении что приводит к застою кровообращения в задненижних отделах легких и к более легкому возникновению пневмонии. Возникновению пневмонии способствуют также другие факторы а именно: несоблюдение эпидемиологического режима то есть инфицирование ребенка; неполноценное питание и плохой уход; охлаждение или перегревание...
78268. НИВЕЛИРОВАНИЕ. ГЕОМЕТРИЧЕСКОЕ НИВЕЛИРОВАНИЕ 27.54 KB
  Одиночные ходы и системы ходов должны опираться не менее чем на два исходных пункта. Проложение замкнутых ходов опирающихся на один исходный пункт допускается лишь при особой необходимости. При приложении нивелирных ходов для определения высот пунктов аналитических сетей относительно исходной основы со средними квадратическими погрешностями...
78269. Тахеометрическая съемкаемка 9. 163.31 KB
  При производстве тахеометрической съемки используют геодезический прибор тахеометр предназначенный для измерения горизонтальных и вертикальных углов длин линий и превышений. Для выполнения тахеометрической съемки используются также тахеометры с номограммным определением превышений и горизонтальных проложений линий. Производство тахеометрической съемки Тахеометрическая съемка выполняется с пунктов съемочного обоснования их называют станциями.
78270. Состав камеральных работ 166.31 KB
  Стороны угла проектируют на лимб с использованием подвижной визирной плоскости зрительной трубы. Она образуется визирной осью трубы при её вращении вокруг горизонтальной оси. Данную плоскость поочередно совмещают со сторонами угла ВА и ВС последовательно направляя визирную ось зрительной трубы на точки А и С...
78271. Определение положения точек земной поверхности, системы координат 125.83 KB
  Определение положения точек земной поверхности системы координат Топографическое изучение земной поверхности заключается в определении положения ситуации и рельефа относительно математической поверхности Земли т. в определении пространственных координат характерных точек необходимых и достаточных для моделирования местности. Модель местности может быть представлена в виде геодезических чертежей изготовление которых называют картографированием и аналитически – в виде совокупности координат характерных точек. Для построения моделей...
78272. Масштабы топографических карт планов 25.89 KB
  Масштаб карты это отношение длины отрезка на карте к его действительной длине на местности. Масштаб от немецкого мера и Stb палка отношение длины отрезка на карте плане аэро или космическом снимке к его действительной длине на местности. Именованный словесный масштаб вид масштаба словесное указание того какое расстояние на местности соответствует 1 см на карте плане снимке. Так как длины линий на местности принято измерять в метрах а на картах и планах в сантиметрах то масштабы удобно выражать в словесной форме...
78273. Нивелирование трассы 50.9 KB
  Закрепление трассы по высоте Вдоль всей разбитой на местности трассы но за пределами зоны работ закрепляются точки называемые реперами. Чтобы не пропустить пикеты и плюсовые точки нивелировщик должен иметь пикетажный журнал трассы. За связующие точки принимают пикеты или плюсовые точки но чтобы расстояние между ними не более 150 м а превышения несколько меньше длины рейки. Нивелирование трассы Отсчеты по рейкам установленным на связующие точки берут в следующей последовательности: 1 по черной стороне рейки на заднюю точку Зч; 2 по...
78274. Условные знаки. Классификация топографических (картографических) условных 37.03 KB
  Условные знаки. Классификация топографических картографических условных знаков Топографические картографические условные знаки символические штриховые и фоновые условные обозначения объектов местности применяемые для их изображения на топографических картах. Для топографических условных знаков предусмотрена общность обозначений по начертанию и цвету однородных групп объектов при этом основные знаки для топографических карт разных стран не имеют между собой особых различий...