4567

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

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

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

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

Русский

2012-11-22

97.5 KB

121 чел.

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

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

ri + 1 = mod(k · ri + bM).

M — модуль (0 < M);

k — множитель (0 ≤ k < M);

b — приращение (0 ≤ b < M);

r0 — начальное значение (0 ≤ r0 < M).

Последовательность случайных чисел, полученных с помощью данной формулы, называется линейной конгруэнтной последовательностью. Многие авторы называют линейную конгруэнтную последовательность при b = 0 мультипликативным конгруэнтным методом, а при b ≠ 0смешанным конгруэнтным методом.

Для качественного генератора требуется подобрать подходящие коэффициенты. Необходимо, чтобы число M было довольно большим, так как период не может иметь больше M элементов. С другой стороны, деление, использующееся в этом методе, является довольно медленной операцией, поэтому для двоичной вычислительной машины логичным будет выбор M = 2N, поскольку в этом случае нахождение остатка от деления сводится внутри ЭВМ к двоичной логической операции «AND». Также широко распространен выбор наибольшего простого числа M, меньшего, чем 2N: в специальной литературе доказывается, что в этом случае младшие разряды получаемого случайного числа ri + 1 ведут себя так же случайно, как и старшие, что положительно сказывается на всей последовательности случайных чисел в целом. В качестве примера можно привести одно из чисел Мерсенна, равное 231 – 1, и таким образом, M = 231 – 1.

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

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

Известен квадратичный метод, предложенный Р. Ковэю:

Известен метод получения случайных чисел, где реализуется последовательность Фибоначчи:

Известен также метод получения случайных чисел, предложенный Грином:

где k- большое число.

Проверка качества работы генератора

От качества работы ГСЧ зависит качество работы всей системы и точность результатов. Поэтому случайная последовательность, порождаемая ГСЧ, должна удовлетворять целому ряду критериев.

Осуществляемые проверки бывают двух типов:

  •  проверки на равномерность распределения;
  •  проверки на статистическую независимость.

Проверки на равномерность распределения

1) ГСЧ должен выдавать близкие к следующим значения статистических параметров, характерных для равномерного случайного закона: 

— математическое ожидание;

— дисперсия;

— среднеквадратичное отклонение.


2) Частотный тест
 

Частотный тест позволяет выяснить, сколько чисел попало в интервал (mr – σrmr + σr), то есть (0.5 – 0.2887; 0.5 + 0.2887) или, в конечном итоге, (0.2113; 0.7887). Так как 0.7887 – 0.2113 = 0.5774, заключаем, что в хорошем ГСЧ в этот интервал должно попадать около 57.7% из всех выпавших случайных чисел (см. рис. 22.9).

Рис. 22.9. Частотная диаграмма идеального ГСЧ
в случае проверки его на частотный тест

Также необходимо учитывать, что количество чисел, попавших в интервал (0; 0.5), должно быть примерно равно количеству чисел, попавших в интервал (0.5; 1).

3) Проверка по критерию «хи-квадрат» 

Критерий «хи-квадрат» (χ2-критерий) — это один из самых известных статистических критериев; он является основным методом, используемым в сочетании с другими критериями. Критерий «хи-квадрат» был предложен в 1900 году Карлом Пирсоном. Его замечательная работа рассматривается как фундамент современной математической статистики.

Для нашего случая проверка по критерию «хи-квадрат» позволит узнать, насколько созданный нами реальный ГСЧ близок к эталону ГСЧ, то есть удовлетворяет ли он требованию равномерного распределения или нет.

Частотная диаграмма эталонного ГСЧ представлена на рис. 22.10. Так как закон распределения эталонного ГСЧ равномерный, то (теоретическая) вероятность pi попадания чисел в i-ый интервал (всего этих интервалов k) равна pi = 1/k. И, таким образом, в каждый из k интервалов попадет ровно по pi · N чисел (N — общее количество сгенерированных чисел).

Рис. 22.10. Частотная диаграмма эталонного ГСЧ

Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно!) по k интервалам и в каждый интервал попадет по ni чисел (в сумме n1 + n2 + … + nk = N). Как же нам определить, насколько испытываемый ГСЧ хорош и близок к эталонному? Вполне логично рассмотреть квадраты разностей между полученным количеством чисел ni и «эталонным» pi · N. Сложим их, и в результате получим:

χ2эксп. = (n1 – p1 · N)2 + (n2 – p2 · N)2 + … + (nk – pk · N)2.

Из этой формулы следует, что чем меньше разность в каждом из слагаемых (а значит, и чем меньше значение χ2эксп.), тем сильнее закон распределения случайных чисел, генерируемых реальным ГСЧ, тяготеет к равномерному.

В предыдущем выражении каждому из слагаемых приписывается одинаковый вес (равный 1), что на самом деле может не соответствовать действительности; поэтому для статистики «хи-квадрат» необходимо провести нормировку каждого i-го слагаемого, поделив его на pi · N:

Наконец, запишем полученное выражение более компактно и упростим его:

Мы получили значение критерия «хи-квадрат» для экспериментальных данных.

В табл. 22.2 приведены теоретические значения «хи-квадрат» (χ2теор.), где ν = N – 1 — это число степеней свободы, p — это доверительная вероятность, задаваемая пользователем, который указывает, насколько ГСЧ должен удовлетворять требованиям равномерного распределения, или pэто вероятность того, что экспериментальное значение χ2эксп. будет меньше табулированного (теоретического) χ2теор. или равно ему.

Таблица 22.2.
Некоторые процентные точки χ2-распределения

p = 1%

p = 5%

p = 25%

p = 50%

p = 75%

p = 95%

p = 99%

ν = 1

0.00016

0.00393

0.1015

0.4549

1.323

3.841

6.635

ν = 2

0.02010

0.1026

0.5754

1.386

2.773

5.991

9.210

ν = 3

0.1148

0.3518

1.213

2.366

4.108

7.815

11.34

ν = 4

0.2971

0.7107

1.923

3.357

5.385

9.488

13.28

ν = 5

0.5543

1.1455

2.675

4.351

6.626

11.07

15.09

ν = 6

0.8721

1.635

3.455

5.348

7.841

12.59

16.81

ν = 7

1.239

2.167

4.255

6.346

9.037

14.07

18.48

ν = 8

1.646

2.733

5.071

7.344

10.22

15.51

20.09

ν = 9

2.088

3.325

5.899

8.343

11.39

16.92

21.67

ν = 10

2.558

3.940

6.737

9.342

12.55

18.31

23.21

ν = 11

3.053

4.575

7.584

10.34

13.70

19.68

24.72

ν = 12

3.571

5.226

8.438

11.34

14.85

21.03

26.22

ν = 15

5.229

7.261

11.04

14.34

18.25

25.00

30.58

ν = 20

8.260

10.85

15.45

19.34

23.83

31.41

37.57

ν = 30

14.95

18.49

24.48

29.34

34.80

43.77

50.89

ν = 50

29.71

34.76

42.94

49.33

56.33

67.50

76.15

ν > 30

ν + sqrt(2ν) · xp + 2/3 · x2p – 2/3 + O(1/sqrt(ν))

xp =

–2.33

–1.64

–0.674

0.00

0.674

1.64

2.33

Приемлемым считают p от 10% до 90%.

Если χ2эксп. много больше χ2теор. (то есть p — велико), то генератор не удовлетворяет требованию равномерного распределения, так как наблюдаемые значения ni слишком далеко уходят от теоретических pi · N и не могут рассматриваться как случайные. Другими словами, устанавливается такой большой доверительный интервал, что ограничения на числа становятся очень нежесткими, требования к числам — слабыми. При этом будет наблюдаться очень большая абсолютная погрешность.

Еще Д. Кнут в своей книге «Искусство программирования» заметил, что иметь χ2эксп. маленьким тоже, в общем-то, нехорошо, хотя это и кажется, на первый взгляд, замечательно с точки зрения равномерности. Действительно, возьмите ряд чисел 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, … — они идеальны с точки зрения равномерности, и χ2эксп. будет практически нулевым, но вряд ли вы их признаете случайными.

Если χ2эксп. много меньше χ2теор. (то есть p — мало), то генератор не удовлетворяет требованию случайного равномерного распределения, так как наблюдаемые значения ni слишком близки к теоретическим pi · N и не могут рассматриваться как случайные.

А вот если χ2эксп. лежит в некотором диапазоне, между двумя значениями χ2теор., которые соответствуют, например, p = 25% и p = 50%, то можно считать, что значения случайных чисел, порождаемые датчиком, вполне являются случайными.

При этом дополнительно надо иметь в виду, что все значения pi · N должны быть достаточно большими, например больше 5 (выяснено эмпирическим путем). Только тогда (при достаточно большой статистической выборке) условия проведения эксперимента можно считать удовлетворительными.

Итак, процедура проверки имеет следующий вид.

  1.  Диапазон от 0 до 1 разбивается на k равных интервалов.
  2.  Запускается ГСЧ N раз (N должно быть велико, например, N/k > 5).
  3.  Определяется количество случайных чисел, попавших в каждый интервал: ni, i = 1, …, k.
  4.  Вычисляется экспериментальное значение χ2эксп. по следующей формуле:

где pi = 1/k — теоретическая вероятность попадания чисел в k-ый интервал.

  1.  Путем сравнения экспериментально полученного значения χ2эксп. с теоретическим χ2теор. (из табл. 22.2) делается вывод о пригодности генератора для использования. Для этого: а) входим в табл. 22.2 (строка = количество экспериментов – 1); б) сравниваем вычисленное χ2эксп. с χ2теор., встречающимися в строке. При этом возможно три случая.

Первый случай: χ2эксп. много больше любого χ2теор. в строке — гипотеза о случайности равномерного генератора не выполняется (разброс чисел слишком велик, чтобы быть случайным).

Второй случай: χ2эксп. много меньше любого χ2теор. в строке — гипотеза о случайности равномерного генератора не выполняется (разброс чисел слишком мал, чтобы быть случайным).

Третий случай: χ2эксп. лежит между значениями χ2теор. двух рядом стоящих столбцов — гипотеза о случайности равномерного генератора выполняется с вероятностью p (то есть в p случаях из 100).

Заметим, что чем ближе получается p к значению 50%, тем лучше.

Проверки на статистическую независимость

1) Проверка на частоту появления цифры в последовательности 

Рассмотрим пример. Случайное число 0.2463389991 состоит из цифр 2463389991, а число 0.5467766618 состоит из цифр 5467766618. Соединяя последовательности цифр, имеем: 24633899915467766618.

Понятно, что теоретическая вероятность pi выпадения i-ой цифры (от 0 до 9) равна 0.1.

Далее следует вычислить частоту появления каждой цифры в выпавшей экспериментальной последовательности. Например, цифра 1 выпала 2 раза из 20, а цифра 6 выпала 5 раз из 20.

Далее считают оценку и принимают решение по критерию «хи-квадрат».

2) Проверка появления серий из одинаковых цифр 

Обозначим через nL число серий одинаковых подряд цифр длины L. Проверять надо все L от 1 до m, где m — это заданное пользователем число: максимально встречающееся число одинаковых цифр в серии.

В примере «24633899915467766618» обнаружены 2 серии длиной в 2 (33 и 77), то есть n2 = 2 и 2 серии длиной в 3 (999 и 666), то есть n3 = 2.

Вероятность появления серии длиной в L равна: pL = 9 · 10L (теоретическая). То есть вероятность появления серии длиной в один символ равна: p1 = 0.9 (теоретическая). Вероятность появления серии длиной в два символа равна: p2 = 0.09 (теоретическая). Вероятность появления серии длиной в три символа равна: p3 = 0.009 (теоретическая).

Например, вероятность появления серии длиной в один символ равна pL = 0.9, так как всего может встретиться один символ из 10, а всего символов 9 (ноль не считается). А вероятность того, что подряд встретится два одинаковых символа «XX» равна 0.1 · 0.1 · 9, то есть вероятность 0.1 того, что в первой позиции появится символ «X», умножается на вероятность 0.1 того, что во второй позиции появится такой же символ «X» и умножается на количество таких комбинаций 9.


 

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

20929. ДОСЛІДЖЕННЯ ОДИНОЧНИХ КАСКАДІВ ТРАНЗИСТОРНИХ ПІДСИЛЮВАЧІВ 97 KB
  Зібрати схему дослідження підсилювача із спільним емітером рис. а BI4 в положення Із спільним емітером ; тумблери В2 В5 В9 BI1 поставити в положення Вкл. Зібрати схему дослідження підсилювача із спільним колектором рис.
20930. ДОСЛІДЖЕННЯ РОБОТИ ІНВЕРТУЮЧОГО І НЕІНВЕРТУЮЧОГО ПІДСИЛЮВАЧІВ 437.5 KB
  Величина напруги вимірюється вольтметром . Набуті значення вихідної напруги занести у відповідні рядки табл.1 і заносячи набуті значення вихідної напруги у відповідні рядки табл. Коефіцієнт підсилення напруги Ku характеризує здатність ОП усилювати диференціальний сигнал що подається на його входи: Вхідна напруга зсуву Uзс обумовлена в основному неідентичністю транзисторів вхідного каскаду ОП.
20931. Функции администратора, настройка параметров безопасности в пакете программ Вертикаль-Технология 1.88 MB
  Цели и задачи: Изучить функции администратора системы научится настраивать права пользователей в пакете программ ВертикальТехнология. После занятия студент должен: Знать: Функции администратора системы методику регистрации пользователей и групп в пакете программ ВертикальТехнология. Уметь: С помощью консоли управления настраивать пакет программ ВертикальТехнология.
20932. Модель технологического процесса в пакете программ Верти 2.79 MB
  Цели и задачи: Изучить методику управления классами модели атрибутами классов управления функциями управления связями между классами и управления фильтрами в пакете программ . После занятия студент должен: Знать: Методику управления классами модели атрибутами классов управления функциями управления связями между классами и управления фильтрами в пакете программ ВертикальТехнология.
20933. Администрирование в приложении «Система трудового нормирования по укрупненым нормам времени» 4.72 MB
  Уметь: Настраивать новые карты трудового нормирования редактировать справочник критериев поиска нормировочных карт настраивать справочные коэффициенты нормировочных карт. Проработать теоретический материал по теме:: администрирование в приложении Система трудового нормирования по укрупненым нормам времени [3] глава 16 [2] лекция №3 Индивидуальное задание: Настроить новую карту трудового нормирования. Система трудового нормирования по...
20934. Установка и настройка системы Вертикаль-Справочник 4.65 MB
  После занятия студент должен: Знать: Порядок установки и настройки Вертикаль Справочника подготовки системы работе. Проработать теоретический материал по теме: Настройка параметров в пакете программ Вертикаль Технология. [1] глава 1 [2] лекция №5 Индивидуальное задание: Настроить доступ индивидуальных пользователей и группы пользователей к ВертикальСправочнику.
20935. Методы работы с базой данных Вертикаль-Справочник 4 MB
  Цели и задачи: Изучить основные методы работы с базой данных ВертикальСправочник. После занятия студент должен: Знать: Основные методы работы с базой данных ВертикальСправочник Уметь: Загружать базы данных в рабочее поле системы; осуществлять поиск информации в базе данных; создавать таблицы типоразмеров; сортировать и заменять данные в таблицах. Для выполнения лабораторной работы необходимо: Проработать теоретический материал по теме: Методы работы с базой данных ВертикальСправочник.
20936. Приложение «Расчет режимов резания» 786 KB
  Уметь: Настроить текущий блок расчета режимов резанья настроить расчет параметров обработки параметров режущего инструмента параметров станка. [1] глава 13 [2] лекция №4 Индивидуальное задание: Настроить текущий блок расчета режимов резанья настроить расчет параметров обработки параметров режущего инструмента параметров станка. Как осуществляется настройка расчета параметров обработки 3. Назначение приложения Приложение Расчет режимов резания...
20937. Модификация структур баз данных, формирование SQL- запро-сов и VB-функций, настройка фильтрации данных в системе Вертикаль-Справочник 4.43 MB
  Цели и задачи: Изучить методику модификации структур баз данных порядок формирование SQL запросов и VBфункций настройку фильтрации данных в системе ВертикальСправочник. После занятия студент должен: Знать: Как отредактировать структуру баз данных и состав таблиц сформировать пользовательские SQLзапросы как настроить фильтрацию данных по различным признакам . Уметь: Подключить несколько таблиц к одному уровню сформировать пользовательские VBфункции настроить фильтрацию данных по различным признакам .