Информационная безопасность - датчики фкн вгу 2013

Датчики последовательности псевдослучайных чисел.

Оглавление

1. Генерация случайных чисел
2. Оценка качества датчиков случайных чисел
3. ТЕСТЫ
Измерение длин L и l датчика псевдослучайной последовательности чисел.
•
•
•
• Тесты на равномерность распределения псевдослучайных чисел
•
• Цифровая равномерность
• Корреляционные свойства последовательности {Ri}
• Проверка решения известной типовой задачи.
4.Датчики случайных чисел
Датчик №1 Датчик№11
Датчик №2 Датчик№12
Датчик№3 Датчик№13
Датчик№4 Датчик№14
Датчик №5 Датчик№15
Датчик №6 Датчик№16
Датчик №7
Датчик №8
Датчик №9
Датчик№ 10
5. Литература

1. Генерация случайных чисел

Генерация случайных чисел необходима для решения задач методом статических испытаний (методом Монте-Карло).
Метод Монте-Карло – это численный способ решения матема-тических задач при помощи моделирования случайных величин.
Метод позволяет, как моделировать любой процесс, на проте-кание которого влияют случайные факторы, так и решать многие не связанные с какими либо случайностями, математические задачи (например, вычисление интеграла), для которых можно придумать вероятностную модель (и даже не одну), позволяющие решать эти задачи.
Т.о. можно говорить о методе Монте-Карло как об универсальном методе решения математических задач. Однако это широкое применение стало возможным только благодаря использованию ЭВМ.
Для реализации метода статических испытаний требуются датчики равномерно распределённых на отрезке [0,1] случайных чисел.
Известны два способа генерации таких чисел:
- физический, например счетчик ?-частиц или электронный ге-нератор белого шума,
- математический:
- использование заранее составленной таблицы случайных чисел;
- вычисление, по какой либо формуле ряда очередных чисел, имитирующих значение случайной величины R. Под словом “имитирующих” понимается, что эти числа удовлетворяют ряду тестов так, как если бы он были значениями этой случайной величины. Такие числа называют псевдослучайными числами.

Достоинства способа генерации случайных чисел вычислением очередного псевдослучайного числа:
- алгоритм (программа) генерирования, как правило, очень коротка;
- скорость генерации имеет порядок скорости работы ЭВМ;
- нужно лишь один раз проверить статистическое «качество» псевдослучайной последовательности чисел несколькими специальными статистическими тестами, не противоречат ли те или иные свойства групп чисел гипотезе о том, что эти числа – значения случайной величины с равномерным распределением. После этого алгоритм генерации псевдослучайных чисел можно безбоязненно использовать при рассчетах методом статистических испытаний.
Для генерации последовательности псевдослучайных чисел, имеющих квазиравномерное распределение, широко используют рекуррентные способы вычисления последующего числа Ri+1 из предыдущего Ri. Это осуществляется с помощью функции преобразования:
Ri+1=Q (Ri) (1.1)

отображающей множество {Ri} на самоё себя.
Задание начального числа R0 в формуле (1.1) определяет псевдослучайную последовательность полностью и однозначно. Но её стохастические свойства аналогичны свойствам случайно выбранных значений.
Все приведённые ниже датчики дают последовательность неповторяющихся псевдослучайных чисел базовой длины L, после которой её часть длины l периодически повторяется. Величину L называют длиной апериода, а l - длиной периода последовательности. Т.о. в базовую длину (апериод) входит и период. Базовая длина – это та начальная длина, которую можно использовать в качестве датчика псевдослучайной последовательности.
Разработано большое количество датчиков случайных чисел, использующих различные формулы и алгоритмы преобразования.
Ниже приводятся различные функции преобразования (1.1), которые не требуют прямых действий с регистрами ЭВМ на уровне машинных команд.

2. Оценка качества датчиков случайных чисел

В программном обеспечении практически всех ЭВМ имеется встроенная функция генерации последовательности псевдослучай-ных квазиравномерно распределённых чисел. Однако для проведения статистического моделирования к генерации случайных чисел предъявляются повышенные требования. Качество результатов такого моделирования напрямую зависит от качества генератора равномерно распределенных случайных чисел, т.к. эти числа являются также источниками (исходными данными) для получения других случайных величин с заданным законом распределения.
К сожалению, идеальных генераторов не существует, а список их известных свойств пополняется перечнем недостатков. Это при-водит к риску использования в компьютерном эксперименте плохого генератора. Поэтому перед проведением компьютерного эксперимента необходимо либо оценить качество встроенной в ЭВМ функции генерации случайных чисел, либо выбрать подходящий алгоритм генерации случайных чисел.
Для применения в вычислительной физике генератор должен обладать следующими свойствами:
1. Вычислительной эффективностью – это как можно мень-шее время вычисления очередного цикла и объём памяти для работы генератора.
2. Большой длиной L случайной последовательности чисел. Этот период должен включать в себя, по крайней мере, необходимое для статистического эксперимента множество случайных чисел. Кроме того, опасность представляет даже приближение к концу L, что может привести к неверным результатам статистического эксперимента.
Критерий достаточной длины псевдослучайной после-довательности выбирают из следующих соображений. Метод Монте-Карло заключается в многократном повторении рассчётов выходных параметров моделируемой системы, находящейся под воздействием входных параметров, флуктуирующих с заданными законами распределения. Основой реализации метода является генерация случайных чисел с равномерным распределением в интервале [0,1], из которых формируются случайные числа с заданными законами рас-пределения. Далее производится подсчёт вероятности моде-лируемого события как отношение числа повторов модель-ных опытов с благополучным исходом к числу общего по-вторения опытов при заданных исходных условиях ( пара-метрах) модели.
Для надёжного, в статистическом смысле, вычисления этой вероятности число повторений опыта можно оценить по формуле:
(2.1)
где - функция, обратная функции нормального распределения, - доверительная вероятность ошибки измерения вероятности.
Следовательно, для того чтобы ошибка не выходила за доверительный интервал ? ? с доверительной вероятностью, например ?=0,95 надо, чтобы число повторений опыта было не меньше:
(2.2)
Например, для 10% ошибки (?=0,1) получим , а для 3% ошибки (?=0,03) уже получим .
Для других исходных условий модели новая серия по-вторений опытов должна проводиться на другой псевдослучайной последовательности. Поэтому либо функция генерации псевдослучайной последовательности должна иметь параметр, изменяющий её (например, R0), либо её длина должна быть не менее:

где K- число исходных условий (точек на кривой определяемой методом Монте-Карло), N- число повторений модельного опыта при заданных исходных условиях, L- длина псевдослучайной последовательности.
Тогда каждая серия из N повторений каждого опыта будет проводиться на своем отрезке псевдослучайной последовательности.
3. Воспроизводимостью. Как указано выше, желательно иметь параметр, изменяющий генерацию псевдослучайных чисел. Обычно это R0. Поэтому очень важно, чтобы измене-ние R0 не портило качества (т.е. статистических параметров) генератора случайных чисел.
4. Хорошими статистическими свойствами. Это наиболее важный показатель качества генератора случайных чисел. Однако его нельзя оценить каким-либо одним критерием или тестом, т.к. не существует необходимых и достаточных критериев случайности конечной последовательности чисел. Самое большее, что можно сказать о псевдослучайной последовательности чисел это то, что она “выглядит” как случайная. Никакой один статистический критерий не является надёжным индикатором точности. По меньшей мере, необходимо использовать несколько тестов, отражающих наиболее важные стороны качества генератора случайных чисел, т.е. степени его приближения к идеальному генератору.
Поэтому, кроме тестирования генератора, чрезвычайно важна проверка его с помощью типовых задач, допускающих независимую оценку результатов аналитическими или численными методами.
Можно сказать, что представление о надёжности псевдослучайных чисел создаётся в процессе их использования с тщательной проверкой результатов всегда, когда это возможно.

3. ТЕСТЫ
Тест№1
Измерение длин L и l датчика псевдослучайной последователь-ности чисел.
Т.к. вычисления по формуле (1.1):
Ri+1=Q (Ri)
являются детерминированным процессом, то максимальная длина Lmax последовательности неповторяющихся чисел определя-ется разрядностью ЭВМ. Если ЭВМ выводит результаты вычисле-ний, например, 8-ми разрядной десятичной дробью, но производит вычисления в сетке 10-ти разрядной дроби, то длина Lmax не может быть больше числа разных возможных значений при вычислении 10-ти разрядной дроби, т.е. Lmax ? 1010. Фактическая длина L Псевдослучайная последовательность начинается с числа R0. Обозначим порядковый номер последнего из неповторяющихся чисел L-1. Тогда в последовательности R0 ,R1 ,R2 ,…,RL-1 все генерируемые числа разные. Этот начальный участок последовательности длины L называют длиной апериодичности (11).

R0 - R1 – R2 ……… Rk …… Ri1 …… RL = Rk…… Ri2 = Ri1 …… Ri
| | | | | | | | | |
0 1 2 k i1 L L+l I

l l

После отрезка апериодичности снова следуют отрезки длины l периодического повторения последовательности чисел. Эти периоды являют собой часть отрезка апериодичности от i=k до i=L-1.
Пусть RL = Rk, тогда периоды l состоят из последовательности Rk, Rk+1,…, RL-1 , являющейся частью отрезка [0,(L-1)]. Таким образом, всегда l Начиная с номера i = L проявляется периодичность:
Ri = Ri-l, для i ? L
l= L-k
Для экспериментального определения длины периодичности l и длины апериодичности L выбираем число i1 априорно настолько большим, чтобы быть заранее уверенным, что i1>k.
Запускаем программу генерации последовательности {Ri} с начального значения R0 и счётчик номеров i.
При i=i1 величину Ri1 запоминаем.
С этого шага все последующие числа Ri1+1, Ri1+2 … и т.д. срав-ниваем с Ri1. Пусть при i=i2 получено первое совпадение Ri2=Ri1. Тогда длина периода l=i2-i1.
Длину апериода L находим путём сравнения двух членов по-следовательности {Ri} ,разнесённых вилкой на интервал l, для чего генерируем одновременно две последовательности {Ri} и {Ri^}, разнесённые на интервал l.
• Шаг i • Шаг i= L, продолжается вычисление {Ri} и начинается вычисление Ri^ = Rl-i, т.е. с начального значения R0.
• На каждом шаге i ? l величины Ri и Ri^ сравниваются. При i= L будет выполняться Ri = Ri^.

Детально реализация этой идеи за один проход программы осуществляется следующим образом:
• Запускается счётчик шагов i.
• Запускается программа вычисления {Ri}. На шаге i=0 вы-полняется операция: R: = R0. Далее на всех последующих шагах выполняется операция: R:=Q(R)
• При i= l включается программа вычисления Ri^, т.е. выполняются операции: R: = Q(R)
R^: = R0
• Начиная с шага i= l+1 и далее работают обе программы:
R: = Q(R)
R^: = Q(R^)
• Начиная с шага i= l производится сравнение Ri^ с Ri
• При шаге i= L произойдёт совпадение Ri^ = Ri
• Задача решена.

Например:

i R

0 _ R0
1 _ R1
2 _ R2
3 _ R3 k=3
4 _ R4
5 _ R5 (i=l=5), R5^=R0?R5 l
6 _ R6 R6^=R1?R6
7 _ R7 R7^=R2?R7
8 _ R8 =R3 R8^=R3=R8 L=8
9 _ R9 =R4
10 _ R10 =R5 l
11 _ R11 =R6
12 _ R12 =R7
13 _ R13 = R8 =R3
14

l = L-k=8-3=5

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

Тесты к- равномерности. [2]

Пусть ?1,?2,?3,…бесконечная последовательность “настоящих” случайных выборочных значений для равномерного распределения на отрезке [0,1].
Разобьём эту последовательность на группы из k величин и обозначим их как k- мерные вектора ?i(k).
Пример разбиения на 3-х мерные вектора:
?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9 ?10 ?11 ?12 …
(?1 ?2 ?3) (?4 ?5 ?6) (?7 ?8 ?9) (?10 ?11 ?12) …
?1(3) ?2(3) ?3(3) ?4(3) ….. ?n(3)

Возьмём единичный k- мерный куб. “Единичный”- означает, что грань куба имеет длину, равную единице (т.е. как раз равна отрезку существования случайной величины ?i). “k- мерный” – означает, что куб имеет k граней.
С вероятностью равной единице вектора ?n(k) равномерно за-полняют единичный k- мерный куб. Это означает, что частота попадания вектора в любую прямоугольную область куба стремится к объёму этой области при n??. Бесконечные последовательности чисел, обладающие такими свойствами, называются k - равномерными.
Ясно, что очень важно проверять k-равномерность псевдослучайных чисел, хотя бы для k=1,2,3,4. Т.к. требуется моделировать случайность, то и проверку следует проводить с помощью статистических критериев, например, критерия хи- квадрат (?2).
Это реализуется следующим образом. Разобьем каждую грань нашего куба на q частей. Т.е. единичный k-мерный куб будет состоять из M= qk одинаковых кубиков с объемом 1/qk каждый.
Пусть m1, m2, …,mM количество точек из последовательности ?1(k), ?2(k), …, ?N(k) попавших в соответствующие кубики. Очевидно:
m1+m2+ …+mM = N
Известно, что для “настоящей случайной” последовательности с равномерным распределением и независимыми векторами ?i(k) величина

является случайной и имеет ?2 распределение с (M-1) степеня-ми свободы.
Поэтому в качестве теста на k-равномерность подсчитываем из реализации псевдослучайной последовательности Ri опытную ?2 величину:
(A)
где mj – количество k-мерных точек (векторов ?n(k), попавших в j-ую ячейку k-мерного куба).

N/M - теоретическая частота попадания случайной величины ?(k) в ячейку k-мерного куба.
1/M - теоретическая вероятность попадания случайной величины ?(k) в любую ячейку.
Вычисленные значения ?2 сравниваем с табличными значениями ?2табл(p,?). Эту величину называют доверительной границей, где:
p – заданный уровень риска (уровень значимости). Его обычно берут в пределах 0,05…0,001.
?=M-2 – число степеней свободы.
Если окажется, что ?2эксп>?2табл , (B), то надо поставить под сомнение гипотезу о том, что наша псевдо-случайная последовательность имеет равномерное распределение и независимые вектора ?(k).
При вычислении по формуле (A) вместо ?i берём Ri.
Выбор N определяется из следующих соображений. С одной стороны следует использовать всю длину L псевдослучайной последовательности тестируемого датчика, т.е. брать N=L/k. С другой стороны, если предполагается использовать последовательность по частям, то надо тестировать k-равномерность всех частей.
Величина q задаёт число M ячеек разбиения куба. Величину M не рекомендуется брать больше . Откуда можно определить q. Однако, при q>10 уже для k=3 объём вычислений становится нереальным. Поэтому приходится брать небольшие значения q, что несколько снижает качество проверки на равномерность.

Тест №2
2.1 Одномерная равномерность

Куб вырождается в отрезок прямой [0,1]. Тест представляется обычной гистограммой. Вектора ?i(1) совпадают с Ri.
Алгоритм:
• Разбиваем отрезок [0,1] на q равных частей. M= q, N=L.

|m1 | m2 | … | mj |… |mM | R1 R2 R3 …… RN 0 1 ?1(1) ?2(1) ?3(1) …… ?N(1) q частей
• Подсчитываем mj попаданий чисел Ri в ячейки куба.
• Вычисляем ?2эксп по формуле (A).
• Принимаем решение по формуле (B).
• Строим график гистограммы.

2.2 Двумерная равномерность

Двумерный куб есть плоскость. Например, при q=6 имеем:

M= q(k)= 62 = 36

Алгоритм:
• Разобьём псевдослучайную последовательность на группы по два: R1 R2 R3 R4 R5 R6 …… RL-1 RL N=L/k=L/2 ?1(2) ?2(2) ?3(2) …… ?N(2)
• Подсчитываем количества m1, m2, …, mM точек ?(2) попав-ших в каждую ячейку плоскости. Длина N подвергаемой тестированию последовательности (части или всей после-довательности) должна быть не меньше M2.
• Вычисляем значение ?2эксп и принимаем решение о гипотезе равномерности.
• Вместо двумерной гистограммы представляем график “звёздного неба”, т.е. картинку расположения N точек ?i(2) на плоскости. Если между точками ?i(2) существует корре-ляция, то она визуально проявляется в виде упорядочения структур расположения точек на плоскости. См. также примечание к тесту 2.2.
2.3 Трёхмерная равномерность
2.4 Четырёхмерная равномерность

Тесты составляются аналогично п. 2.1 и 2.2.

Тест №3
Вычисление коэффициентов неравномерности

Коэффициенты неравномерности распределения генерируе-мых псевдослучайных чисел вычисляются в процентах по формуле:

mj – количество чисел ( точек ?i( 1) ) попавших в j-ую ячейку гистограммы.
M – количество ячеек гистограммы.
N/M– среднее ожидаемое количество случайных чисел попадающих в ячейку гистограммы.
Этот тест удобно применять для сравнения датчиков между собой на равномерность гистограммы, т.е. на одномерную k –равномерность. В [4] приведены данные сравнения датчиков по Kн для микрокалькуляторов МК-52 и МК-61. Описание приведённых в таблице датчиков см. ниже.

Номер датчика 6 7 5
Kн, % 11,1 7,7 6,9

Для датчиков 6 и 7 коэффициенты Kн представлены для N=1000 и M=10. Для датчика 5 N=37, и R0=0.1234567.

Цифровая равномерность

Тест №4
4.1 Одномерная цифровая равномерность

Пусть случайные числа представлены 8-разрядной дробью. Берём числа и строим гистограмму для каждого разряда в отдельности. Например, строим гистограмму для первого после запятой разряда. Из N чисел Ri подсчитываем, сколько раз в первом разряде появляется цифра 0, затем – цифра 1и т.д. до цифры 9. Получаем гистограмму для первого разряда.

Частота появления цифры в 1-ом разряде

0 1 2 3 4 5 6 7 8 9 циф ра

Гипотезу о равномерности распределения цифр в 1-ом разряде проверяем критерием хи-квадрат.
4.2 Двумерная цифровая равномерность
Разряды после запятой числа Ri разбиваем на группы по два разряда: Ri= a0,| a1 a2| a3 a4 | a5 a6 | a7 a8 |
Для каждой пары разрядов строим гистограмму (всего 4 гистограммы) и оцениваем равномерность гистограммы критерием хи-квадрат.
Гистограмму для пары разрядов строим следующим образом. Пару разрядов рассматриваем как целые числа ?( 2), принимающие значения от 0 до 99. На оси гистограммы представляем 10 ячеек для каждого десятка чисел ?( 2):

0 10 20 30 40 50 60 70 80 90 99

Строим гистограмму, например, для первой после запятой пары разрядов. Берём N чисел Ri и подсчитываем частоту mj, j=0,1,…,9 или частость mj/N попадания чисел ?(2) в каждый интер-вал гистограммы, уславливаясь относить круглые (в смысле деся-ток) числа к определённому интервалу, так чтобы каждый интервал состоял из 10 чисел. Например, ?(2)=30 следует относить к интервалу m3, см. рисунок.

4.3 Трёхмерная и четырёхмерная цифровая равномерность

Тестируется аналогично.

Тест №5
Корреляционные свойства последовательности {Ri}

Вычисляем статистические оценки коэффициентов корреля-ции c(k) для пар вида (Ri, Ri+k) и определяем насколько значимо они отличаются от нуля. Заметим, что из (k+1)-мерной равномер-ности следует, что c(k)=0. Но обратное конечно неверно.

Ri- i член последовательности {Ri}.
- для каждого конкретного значения k это сумма всех возможных произведений Ri* Ri+k делённая на число произведений.
Если Ri и Ri+k не коррелированны, то:

и, следовательно: c(k)=0.

Тест №6
Проверка решения известной типовой задачи.

Алгоритм:
• Генерируем последовательность {Ri}, i=0,1,…N-1.
• На каждом шаге генерации вычисляем величину:

• Если r

Т.е. получаем:
• По данным счётчика c и заданной величине N вычисляем экспериментальное значение числа ?: ?эксп=8*с/N
• Сравнивая ?эксп с табличным “истинным” значением определяем, сколько верных знаков ? можно вычислить с помощью нашего датчика. Очевидно, что следует брать N=L.
R2i+1

1

c
r

0 1 R2i

____________________________________________________
Примечание к тесту 2.2.
Интересно строить “звёздное небо” также и парами чисел Ri разнесёнными на k шагов при последовательном изменении i=0,1,… Т.е. парами: (Ri , Ri+k )

Для k=1 Для k=2
R0 R1 R0 R2
R1 R2 R1 R3
R2 R3 R2 R4
… …

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

Датчик №1: Метод Неймана.

Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Его называют методом середины квадратов.
Пусть задано 4-значное число R0=0.9876. Возведём его в квадрат. Получим 8-значное число R02=0.97535376. Выберем 4 средние цифры из этого числа и положим R1=0.5353. Затем снова возведём в квадрат и извлечём из него 4 средние цифры. Получим R2 и т.д. Этот алгоритм не оправдал себя. Получалось больше чем нужно малых значений Ri.
Однако, представляет интерес исследовать качество этого генератора со смещённой вправо группой выбора цифр у Ri2:

где a-максимальная значность дроби для данной ЭВМ (например, а=8).
b-количество знаков после запятой в числе Ri (например, 5).
INT (А)- целая часть числа.
Для a=8, b=5, R0=0.51111111 на ПК ZX-Spectrum получается около 1200 неповторяющихся чисел.

Задание: Исследование следует проводить при варьировании а, b, R0. Найти при каких величинах a, b, R0 получается наибольшая длина L последовательности неповторяющихся чисел при “хороших” стохастических параметрах. Установить влияет ли величина R0 на качество датчика. Если влияет, то определить область “приемлемых” значений параметра R0. Представить результаты тестирования оптимального варианта значений a, b, R0.

Мультипликативные алгоритмы.
Датчик №2: Линейный конгруэнтный генератор Лемера 1951.

где Ui, M, C и p–целые числа.
A mod B- остаток от деления нацело A на B,

A mod B =A-B*INT (A/B)

Генерируемая последовательность имеет повторяющийся цикл не превышающий p чисел.
Максимальный период получается при C?0, но такой генератор даёт плохие стохастические результаты [3].
При C=0 генераторы называют мультипликативными. Они имеют лучшие стохастические параметры. Формулы их использования называют ещё методом вычетов.
Наиболее популярным для получения псевдослучайных чисел является метод вычетов по такой формуле [2]:

где Ui, M, p-целые числа, 0 Если выбрать U0 и M такими, чтобы для R0=U0/p получалась несократимая дробь и взять p и M взаимно простыми, тогда все Ri будут несократимыми дробями вида: Ri= Ui/p.
Получим наибольшую (но не более p) длину неповторяющейся последовательности чисел. Значения U0, p и M удобно выбрать из простых чисел.

Задание: Исследовать при каких U0, p и M длина последова-тельности неповторяющихся чисел будет не менее 10000 при «хо-роших» стохастических параметрах. Определить влияет ли величина R0 при M и p= const на статистические характеристики датчика. Если влияет, то определить область допустимых величин U0. Представить результаты тестирования генератора для оптимальных величин p, M и U0.

Датчик №3: Модификация Коробова [9].

где p- большое простое число, например 2027, 5087, …
М - целое число, отвечающее условиям:

n – целое число. Т.е. выбираем M близким к p/2 из множества чисел M = p – 3n .
Например, для p=5087 берём n=7. Потому что 37=2187, а 38=6561 будет уже больше p. Итак: М=5087-2187=2900.
Получаем числа Ui в интервале [1,p-1]=[1,5086] и числа Ri в интервале (0,1).

Задание: Подобрать M и p при которых получаются лучшие статистические параметры датчика и наибольшая длина L. Выяснить влияет ли величина R0 на стохастические характеристики датчика и, если влияет, то определить область допустимых значений R0. Представить результаты тестирования датчика для оптимальных значений M, p и R0.

Другие формы вычетов.

Датчик №4:
Ri+1 = FRAC(M*Ri), R0 = u / p (4.1)
где FRAC(A)=A-INT(A)- есть дробная часть числа А.
p и M-специально подобранные целые постоянные.
Значение u (u-целое число, u

Смысл формулы состоит в следующем: Разложим R0 в бесконечную М-ичную дробь, т.е. дробь по степеням M-k:
(4.2)
где ak принимает одно из возможных значений 0, 1, …M-1.
Теперь:
R1 = FRAC(M*R0) = 0,а2а3…
R2 = FRAC(M*R1) = FRAC(M*0,a2a3...)=0,a3a4…=FRAC(M2*R0)
…………………………………………………………(4.3)
Ri = FRAC(Mi * R0) = 0,ai + 1 ai + 2 …

Т.е. операция получения Ri состоит в перенесении запятой в R0 на i позиций вправо и отбрасывании целой части.
Для того, чтобы дробь (4.2) была бесконечной необходимо, чтобы выражение R0=u/p являло собой несократимую дробь.
Например, возьмём p=2m, m-целое число. Тогда для того, чтобы u и p были взаимно простыми достаточно выбрать u таким, чтобы в разложении его на простые сомножители среди них не встречался бы множитель 2. Можно выбирать u и p взаимно простыми и другими способами.
Примечание: Многие специалисты [2] исследовали и проверяли псевдослучайную последовательность двоичных чисел Vi:
Vi :=FRAC(M * Vi)
V0 := 2 – m (4.4)
m-число двоичных разрядов мантиссы ячейки ЭВМ.
Они брали множитель M вида:
M = 52 q + 1 , q-целое число.
Согласно формуле (4.3) имеем:
Vi = FRAC(5i*(2 q+1) , (4.5)
Опишем получение последовательности величин Vi аналогично алгоритму (4.1), (4.2).
Запишем дробь V0=2 – m в системе счисления с основанием 5:
(4.6)
где ak принимает одно из значений: 0, 1, 2, 3, 4.
Соотношение (4.5) означает, что запятая в (4.6) переносится на (2q+1)*i позиций вправо и целая часть полученного числа отбрасывается. Отсюда ясно, что при малых 2q+1 величины Vi, Vi+1 будут заметно зависимыми. Поэтому рекомендуется брать q максимальным из тех, для которых выполняется условие:
(4.7)
Методами теории чисел можно показать, что для указанных параметров M, V0 длина последовательности будет:

Величина 52q+1 в двоичном виде оканчивается на 01. Поэтому все Vi есть двоичные дроби, последние два разряда которых равны 01.
Вследствии равенства L=2m-2 остальные m-2 разряда пробегают все возможные значения (комбинации).
Поэтому в качестве V0 можно брать любую m-разрядную двоичную дробь такого типа.
Этот метод вычетов реализован программой в машинных кодах на ЭВМ М-220 и БЭСМ-6.
Величины М и m взяты равными соответственно:
M=515 и 517 и m=36 и 40.
Для БЭСМ-6 длина L?2*1011.

Задание: Исследовать как влияют величины M, u и p формулы (4.1) на стохастические качества и на длины L и l последовательности псевдослучайных чисел этого датчика.
Определить влияет ли R0 на статистические параметры датчика и, если влияет, то найти допустимую зону задания R0. Представить результаты тестирования датчика для его оптимальных параметров.

Датчик №5
В [5], [6] предлагается в формуле(4.1) выбирать M и R0 сле-дующими способами:
Способ 1: M=8t?3, t- целое число.
R0- любое нечётное число, меньшее 1,т.е. дробь вида 0,xxxxxxн, н - нечётная цифра.
В [6] рекомендуется брать M=37. Однако, такой датчик заметно меняет свои статистические характеристики при изменении R0.
Способ 2: M=16q+11, q-целое число.
R0 - любое нечётное число меньшее 1. Например, при M=91, R0=0.11111111 получается L?10000.

Задание: Исследовать такими способами выбираемых констант их влияние на стохастические качества датчика и длины l и L последовательности псевдослучайных чисел. Посмотреть также, как влияет выбор чётного R0. Установить влияет ли R0 на параметры датчика и, если влияет, то оценить область приемлемого значения R0. Представить результаты тестирования датчика с подобранными оптимальными параметрами.

Датчик №6 [4], [7]

При R0=0.5 получается около 8000 неповторяющихся чисел.
При R0=0.002 получается около 9000 неповторяющихся чисел.

Задание: Исследовать влияние выбора R0 на стохастические качества датчика и длины l и L псевдослучайной последовательно-сти. Можно попробовать заменить константу 11 на другое простое число не большее 100. Представить результаты тестирования датчика для нескольких R0.

Датчик №7 Датчик со счётчиком [5], [7]

(7.1)

где n- константа, целое число, определяемое типом ЭВМ;
z0, R0- любые числа, меньшие 1;
Для z0=0.011 и R0=0 для программируемого калькулятора получается около 8*107 неповторяющихся чисел.

Задание: исследовать влияние выбора величин n, z0, R0 на стохастические параметры датчика и на длины L и l псевдослучайной последовательности чисел. Установить влияет ли величина R0 на качество датчика и, если влияет, то определить область допустимых величин R0. Представить результаты тестирования датчика при оптимальных значениях n, z0, R0.

Тригонометрические алгоритмы.
Основаны на использовании ошибки вычисления косинуса больших аргументов.

Датчик №8 [7]

где n-целое число, определяемое типом ЭВМ. Например, для программируемого микрокалькулятора n=9. Для ПК ZX-Spectrum n=4.
R0 - любое число меньшее 1.

Задание: исследовать влияние величин n и R0 на стохастиче-ские характеристики датчика и на длины l и L псевдослучайной последовательности. Определить оптимальную, в смысле качества и максимальной длины L, величину n. Установить влияет ли R0 на качество датчика и, если влияет, то найти допустимые пределы изменения R0. Представить результаты тестирования датчика при оптимальной величине n.

Датчик №9: Тригонометрический алгоритм со счётчиком [7].

На программируемом микрокалькуляторе получается 109 неповторяющихся чисел.

Задание: Установить влияет ли величина R0 на качество датчика. Представить результаты тестирования датчика для нескольких R0.

Датчик №10: Алгоритм со счётчиком [5].

Ri+1 = (1/?)*arccos(cos(10n – 1)*Ri)
где n-целое число, определяемое типом ЭВМ. Для программируемого микрокалькулятора n=8. Получается около 108 неповторяющихся чисел. Для ПК ZX-Spectrum n=4.

Задание: Подобрать оптимальную, в смысле хорошего качества и длин l и L, величину n. Установить влияет ли величина R0 на качество датчика и, если влияет, то найти допустимую область изменения R0. Представить результаты тестирования датчика для оптимальной величины n и нескольких R0.

Датчик № 11. Линейный генератор ПСП по Хофману.

Ui = (a? Ui – 1 + b) mod p, при p = 22, k – целое > 2
b - нечетное
a mod 4 = 1.
Или:
Ui = [(2a + 1)? Ui – 1 + c ] mod 2 k, k ? 35, c – нечетное , i = 1, 2, 3, . . .
Задание. Исследовать при каких величинах параметров: U0, k, a и c длина ПСП неповторяющихся чисел не менее 10000, при хаотическом тесте «звёздное небо» (т.е. без решетчатой структуры). Для этих зафиксированных параметров провести остальные тесты.

Датчик № 12. Формула динамического хаоса.
Ui + 1 = a? Ui ? (1 – Ui) a – целое число ? 4.
Задание. Определить граничное значение а граничное, чтобы область определения Ui лежала в интервале 0 Провести датчик через все тесты.
Для а > аграничное протестировать ПСП чисел Ri = Ui / Ui max.

Датчик №13. BBS – генератор ПСП, предложенный Э. Блюм, М. Блюм и М. Шуба (1999год). [13]
Пусть P и Q два больших целых простых числа примерно одинакового размера:
P ? 3 (mod 4), Q ? 3(mod 4).
Тогда число N = P?Q называют числом Блюма.
Формула ПСП:
Ui + 1 = Ui2 mod N.
«Хорошие» стохастические свойства ПСП получаются при
N = 28 565 461.
Задание. Провести генератор Блюма через все тесты.
Определить минимальное значение N, при котором длина ПСП получается не менее 10 000 при отсутствии решетчатой структуры теста «Звездное небо».

Датчик №14. ПСП генераторы Фибоначчи. [13].
Аддитивный генератор:
Ui + 1 = (Ui + Ui -1 ) mod p i = 0, 1, 2, 3, . . .
Аддитивный генератор с запаздыванием:
Ui = (Ui – k + Ui –q ) mod p , p – чётное , i = 0, 1, 2, . . .
Параметры генератора: p и начальные значения Ux.
Задание. Определить при каких величинах параметров обеспечивается длина ПСП не менее 10 000, при отсутствии решетчатой структуры теста «Звёздное небо».
Провести генератор ПСП Фибоначчи через остальные тесты.
«Хорошие» результаты (какие?) получаются при:
Ui + 1 = (Ui + Ui – 1) mod 11 979.
Ui = (Ui - 3 + Ui – 7) mod 256.

Датчик №15. Инверсный генератор ПСП [13].

Ui+1 = ( a?Ui-1 + b) mod P, P – простое число.
«Хорошие» результаты тестирования получаются при: a = 5 830, b = 402, P = 8191.
Задание. Проверить генератор с рекомендуемыми параметрами всеми тестами.
Определить при каких параметрах длина ПСП получается не менее 10 000 при отсутствии решетчатой структуры теста «Звёздное небо».

Датчик №16. Датчик ПСП чисел Дж. Марсалья – мультипликативный вариант генератора Фибоначчи с запаздыванием [13]:
Ui = (Ui – k ? Ui – q ) mod p, где p – четное, а U0, . . .Uq – 1 - целые нечетные числа, сравнимые с 1 по модулю 4.
Задание. Определить при каких параметрах ( p, U0, . . .Uq – 1) получается длина ПСП не менее 10 000, при отсутствии решетчатой структуры теста «Звёздное небо».
Провести генератор ПСП через остальные тесты.

Литература
1. Соболь И.М. Метод Монте-Карло. –М: Наука,1972.
2. Михайлов Г.А. Некоторые вопросы теории методов Монте-Карло. –М.:Наука,1974.
3. Хеерман Д.В. Методы компьютерного эксперимента в теоретической физике. –М: Наука,1990.
4. Стрельянов А.И. Производство вычислений на программируемых микрокалькуляторах МК-52, МК-54, МК-61. –М: Машиностроение,1990.
5. Дьяконов В.П. Справочник по рассчётам на микрокалькуляторах, изд. 3. –М: Наука,1989.
6. Дьяконов В.П. Рассчёт нелинейных и импульсных устройств на программируемых микрокалькуляторах. –М: радио и связь,1984.
7. Епанечников В.А., Цветков А.Н. Справочник по прикладным программам для микрокалькуляторов. –М: Финансы и статистика,1988.
8. Цветков А.Н., Епанечников В.А. Прикладные программы для микроЭВМ «Электроника» Б-3, МК-54, МК-56. –М: Финансы и статистика,1984.
9. Астанин Л.Ю. и др. Применение программируемых калькуляторов для инженерных и научных рассчётов. –М: Энергоиздат,1986.
10. Х. Гулд, Я. Тобочник Компьютерное моделирование в физике, том2. –М: Мир,1990. §11.6 Случайные числа.
11. Полляк Ю.Г. Вероятностное моделирование на ЭВМ. –М: Сов. Радио,1971. Гл.2,стр. 66-112.
12. Дьяконов В.П. Справочник по алгоритмам и программам на языке Бейсик для персональных ЭВМ. –М: Наука,1987.
13. Иванов М. А., Чугунов И. В. Теория, применение и оценка качества генератора псевдослучайных последовательностей – М,: Кудиц Образ, 2003.