allgosts.ru03. УСЛУГИ. ОРГАНИЗАЦИЯ ФИРМ, УПРАВЛЕНИЕ И КАЧЕСТВО. АДМИНИСТРАЦИЯ. ТРАНСПОРТ. СОЦИОЛОГИЯ.03.120. Качество

ГОСТ Р ИСО 28640-2012 Статистические методы. Генерация случайных чисел

Обозначение:
ГОСТ Р ИСО 28640-2012
Наименование:
Статистические методы. Генерация случайных чисел
Статус:
Действует
Дата введения:
12/01/2013
Дата отмены:
-
Заменен на:
-
Код ОКС:
03.120.30

Текст ГОСТ Р ИСО 28640-2012 Статистические методы. Генерация случайных чисел



ФЕДЕРАЛЬНОЕ АГЕНТСТВО

ПО ТЕХНИЧЕСКОМУ РЕГУЛИРОВАНИЮ И МЕТРОЛОГИИ


НАЦИОНАЛЬНЫЙ

СТАНДАРТ

РОССИЙСКОЙ

ФЕДЕРАЦИИ


ГОСТ Р исо 28640—

2012


Статистические методы ГЕНЕРАЦИЯ СЛУЧАЙНЫХ ЧИСЕЛ

ISO 28640:2010

Random variate generation methods (IDT)

Издание официальное

2014

Предисловие

1    ПОДГОТОВЛЕН Автономной некоммерческой организацией «Научно-исследовательский центр контроля и диагностики технических систем• (АНО «НИЦ КД») на основе собственного аутентичного перевода на русский язык международного стандарта, указанного в пункте 4

2    ВНЕСЕН Техническим комитетом по стандартизации ТК125 «Статистические методы в управлении качеством продукции»

3    УТВЕРЖДЕН И ВВЕДЕН В ДЕЙСТВИЕ Приказом Федерального агентства по техническому регулированию и метрологии от 29 ноября 2012 г. No 1274-ст

4    Настоящий стандарт идентичен международному стандарту ИСО 28640:2010 «Методы генерации случайных чисел» (ISO 28640:2010 «Random variate generation methods»).

Наименование настожцего стандарта изменено относительно наименования указанного международного стандарта для приведения в соответствие с ГОСТ Р 1.5 (подраздел 3.5).

При применении настоящего стандарта рекомендуется использовать вместо ссылочных международных стандартов соответствующие им национальные стандарты Российской Федерации, сведения о которых приведены в дополнительном приложении ДА

5    ВВЕДЕН ВПЕРВЫЕ

Правила применения настоящее о стандарта установлены в ГОСТ Р 1.0—2012 (раздел 8). Инфор• мация об изменениях к настоящему стандарту публикуется в ежегодном (по состоянию на 1 января текущего года) информационном указателе «Национальные стандарты». а официальный текст изменений и поправок — в ежемесячном указателе «Национальные стандарты». В случае пересмотра (замены) или отмены настоящего стандарта соответствующее уведомление будет опубликовано в ближайшем выпуске ежемесячного информационного указателя «Национальные стандарты». Соответствующая информация, уведомление и тексты размещаются также в информационной системе общего пользования—на официальном сайте Федерального агентства по техническому регулированию и метрологии в сети Интернет (gost. ги)

©Стандартуыформ. 2014

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

Содержание

СЛ К) К)


4    Условные обозначения и математические операции над двоичными числами

5    Псевдослучайные числа (равномерное распределение)...........

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

Приложение ДА (справочное) Сведения о соответствии ссылочных международных стандартов

Введение

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

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

Существует шесть основных направлений использования рандомизации.

•    отбор случайной выборки;

•    анализ выборочных данных:

•    разработка стандартов:

- проверка теоретических результатов:

•    проверка того, что предложенная процедура соответствует заявленным свойствам:

•    принятие решений е условиях неопределенности.

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

Применяемый в настоящем стандарте международный стандарт разработан Техническим комитетом ИСО/ТС 69 «Применение статистических методов».

НАЦИОНАЛЬНЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ

Статистические методы ГЕНЕРАЦИЯ СЛУЧАЙНЫХ ЧИСЕЛ Statistical methods. Random vanate generation

Дата введения — 2013—12—01

1    Область применения

8 настоящем стандарте установлены методы генерации случайных чисел, подчиняющихся равномерному и другим законам распределения, используемых при применении метода Монте-Карло. В настоящий стандарт не включены криптографические методы генерации случайных ч*сел. Настоящий стандарт будет полезен в первую очередь:

•    научным работникам, технологам и слециа/мстам в области систем управления, использующим статистическое моделирование;

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

•    математикам, разрабатывающим сложные процедуры оптимизации с использованием метода Монте-Карло;

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

2    Нормативные ссылки

8 настоящем стандарте использованы нормативные ссылки на следующие стандарты:

ИСОУМЭК 2382-1 Информационная технология. Словарь. Часть 1. Основные термины (ISO/IEC 2382-1. Information technology — Vocabulary — Part 1: Fundamental terms)

ИСО 3534-1 ;2006 Статистика. Словарь и условные обозначения. Часть 1. Общие статистические термины и термины, используемые в вероятностных задачах (ISO 3534-1:2006. Statistics — Vocabulary and symbols — Part 1: Probability and general statistical terms)

ИСО 3534-2:2006 Статистика. Словарь и условные обозначения. Часть 2. Прикладная статистика (ISO 3534-2:2006. Statistics — Vocabulary and symbols — Part 2: Appfeed statistics)

3    Термины и определения

В настоящем стандарте применены термины по ИСО/МЭК 2382-1. ИСО 3534-1. ИСО 3534-2. а также следующие термины с соответствующими определениями:

3.1 случайное число (random variate, random number): Число, представляющее собой реализацию случайной величины.

Примечание 1 — Термж «случайное число» часто испогъзуют по огношеюео к равномерно распределенной случайной величине.

Примечание 2 — Случайные числа, представление в виде последовательности, называют пос-ледоватетьностыо случайных чисел.

Издание официальное

3.2    псевдослучайное число (pseudorandom number): Число, полученное е соответствии с задан* ным алгоритмом, используемое в качестве случайного числа.

Примечание — В ситуациях, когда из контекста ясно, что речь идет о псеедослучайтх числах, псевдослучайное «мело иногда называют «случайным «мелом».

3.3    физическое случайное число (physical random number): Случайное число (3.1), полученное на основе некоторого физического явления.

3.4    двоичная последовательность случайных чисел (binary random number sequence): Последовательность случайных чисел (3.1 X состоящая из нулей и единиц.

3.5    начальное число (seed): Исходное число, необходимое для начала генерации псевдослучай* иых чисел.

4    Условные обозначения и математические операции над двоичными числами

4.1    Условные обозначения

8 настоящем стандарте применены обозначения по ИСО/МЭК 2382*1. ИСО 3534*1, ИСО 3534*2. а также следующие условные обозначения и сокращения:

X — целое равномерно распределенное случайное число (целое случайное число, подчиняющееся равномерному распределению);

U — стандартное (из интервала [0,1])равномерно распределенное случайное число (случайное число из интервала [0.1). подчиняющееся стандартному равномерному распределению);

Z — нормальная случайная величина (случайная величина, подчиняющаяся нормальному распределению);

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

4.2    Математические операции над двоичными числами

8 настоящем стандарте использованы следующие математические операции над двоичными числами:

mod (m: к) — остаток от деления целого числа т на целое число к:

m @ к — побитовая логическая операция над двоичными целыми числами ши к «исключающее ИЛИ».

/Гример 1 — Правила побитовой логической операции ф 1Ф1-0.

0Ф1-1,

1Ф0-1.

0Ф0-0.

/Гример побитовой логической операции ф: 1010 ф 1100-0110:

т а к — побитовая логическая операция «И» над двойными целыми числами т и к.

/Гример 2 — Правила побитовой логической операции т л к 1 л 1-1.

0Л1-0.

1 /\ 0-0.

0л0-0.

Пример побитовой логической операции л‘- 1010 л 1100 = 1000:

т :- к — замена значения т на значение к: т » к — сдвиг вправо двоичного целого числа т на к битое: m « к — сдвиг влево двоичного целого числа m на Jr битое.

5    Псевдослучайные числа (равномерное распределение)

5.1 Общие положения

В данном подразделе приведены алгоритмы генерации псевдослучайных чисел, соответствующих равномерному распределению, основанные на методах М-последовательности (см. 5.2).

8 приложении А для информации приведен принцип генерации физических случайных чисел.

В приложении В приведены тексты компьютерных программ для всех рекомендуемых алгоритмов. Несмотря на то. что линейный конгруэнтный метод не рекомендован для решения сложных задач модели* роеания методом Монте-Карло, он также включен в приложение В для информации.

5.2    Метод М-последовательности

a)    Для натурального числа р и чисел с,. с2. —. с^, принимающих значения 0 или 1. определяют рекуррентную формулу

= срл Wi * ср-2 Х^Р.2    ♦ с, V. ♦    2) (л = 1.2. 3....).

b)    Наименьшее положительное целое N. такое, что х„.« = х„ для всех значений п называют периодом последовательности. Эту последовательность называют М-лоспвдователькостью. период которой составляет {2е-1).

c)    Полином

f* ♦ см1 ♦ - ♦ С„ ♦ 1

является характеристическим полиномом для приведенной выше рекуррентной формулы.

Примечание 1 — Необходимым и достато ■ ьм условием того, что приведенная в перечислен mi а) формула может быть испогъэоеана для генерации М-последовательности является то. что хотя бы одно из начальных чисел х,. х2р отлично от нуля.

Примечание 2 — Буква М в обозначен»** М-последовагальности является первой буквой ангпм-ооого слова «maximum» (наибогъший). Период любой последовательности, сгенерированной по приведенной в перечислении а) рекуррентной формуле, не может быть больше (У - 1). Поэтому, если есть ряд с периодом (2* - 1), это ряд с наибольшим периодом.

Примечание 3 — При использовании дамчого метода в качестве характеристического полинома применяют иги один из погамомов. приведенных в тэбгице 1. или другой, более простой полином из справочной гмтературы. а его коэффициенты используют е формуле перечисления а).

5.3    Пятипараметрический метод

Данный метод использует характеристический полином из 5 членов и позволяет генерировать последовательности w-битовых двоичных целых чисел в соответствии со следующей рекуррентной формулой. Такой алгоритм называют GFSR1 ’ или генератором случайных чисел «сдвиговый регистр с обратной связью».

© *в<д = 1. 2. 3...).

Параметры (р. qt, q2.    *0 и X,..... Хв первоначально задают как начальные числа. Примеры пара

метров р. g,. q2. рз с наибольшим периодом (2* -1) приведены в таблице 1.

Таблица 1 — Пяти параметрические характеристические полююмы

p

ч,

Ъ

89

20

40

69

107

31

57

82

127

22

63

83

521

86

197

447

607

167

307

461

1279

339

630

988

2203

585

1197

1656

2281

577

1109

1709

3217

809

1621

2381

4253

1093

2254

3297

4423

1171

2273

3299

9689

2799

5463

7712

Примечание — Qi- Чг- <h являются показателями степени ненулевых член» характеристического полинома.

1 * GFSR — Generalized Feedback Shift Register.

5.4 Комбинированный метод Таусворта

При генерации случайных чисел методом Таусеорта используют рекуррентную формулу

Vр = <хп.0 ♦ *„) (mod 2). (л = 0.1.2....),

где Xq, xt. х2.... — соответствующая W-последовательность.

При использовании такой М-последовательности последовательность w-битовых целых чисел, называемую простой последовательностью Таусеорта с параметрами (р. q. 0. получают по формуле

5••• (Л = 0.1.2,...),

где t —натуральное число взаимно простое с периодом (2е -1) М-последовательности; w — длина слова, не превышающая р бит.

Период этой последовательности составляет (2е -1).

Примечание 1 — Два цегых числа являются взаимно простыми или огноситегъно простыми, есгы у них нет общих дегытелей кроме единицы,

/пример — Если в качестве исходного выбран многочлен tf* Г *1, установлены параметры р=4 и q=1 и в приведенной выше рекуррентной формуле заданы начальные числа (х^. Jfj.Xj, х3)-(1,1,1,1). то М-последовательность. полученная в соответствии с рекуррентной формулой, будет иметь вид: 1,1,1.1. О.О.О.1. 0.0.1.1, 0.1.0,1. 1.1.1.О. .... с периодом (2* - 1) - 15. В случае t - 4 (4 является взаимно простым числом по отношению к 15) и w-4 простая последовательность Таусворта {Х„}с параметрами (4, 1. 4) имеет вид

Хс0х1х2х3 = 1111 (= 15).

X, = х4 х5 Х( х7 = 0001 (- 1).

Х2 = х$ х3 х19 ж„ = 0011 (= 3).

Х3 = Хц х13 Хм х9 - 0101 (— 5),

Х4 = х, х2 х3 х4 = 1110 (= 14).

Xs = х5 хв х7 Xj = 0010 (= 2).

Простая последовательность Таусеорта. полученная таким образом в десятичных числах, имеет вид: 15, 1. 3. 5. 14. Z 6. 11. 12. 4. 13. 7. в. 9, 10, 15.1. 3,.... с периодом (2* - 1)- 15.

Если имеется несколько, например. J простых последовательностей Таусворта {Хлл} ,/ = 1,2,__J

с одной и той же длиной слова w. комбинированный мвтсщ Таусворта генерирует последовательность псевдослучайных чисел {XJ как результат побитовой операции «исключающее ИЛИ» при двоичном представлении чисел в этих J последовательностях.

х, = x(i\ © Xе». © ... ©Х^. (л s 0.1. 2....).

Параметры и начальные числа комбинировало* последовательности Таусеорта представляют собой комбинацию параметров и начальных чисел каждой простой последовательности Таусеорта. Если периоды J простых последовательностей Таусеорта являются взаимно простыми, то период комбинированной послед оватегьм ости Таусворта равен произведению периодов Jпоследовательностей.

Примечание 2 — Данный метод может генерировать последовательности чисел многомерного равномерного распределения. Алгоритм taus88_31(). приведенный а приложении А. позволяет генерировать последовательность 31-битовых целых чисел, комбинируя три простых генератора Таусворта с параметрами (р. д. 0 равными (31. 13. 12). (29. 2. 4) и (28. 3. 17) соответственно. Длина периода комбжированию* последовательности (231 - 1) (229 - 1) (23* - 1). т. е. прибгмзительно 2м. Другие комбинации предложены в [7] и (8).

5.5 Метод Мврсенна Твистера

Метод Мерсенна Твистера позволяет генерировать последовательность двоичных псевдослучайных целых «-битовых чисел в соответствии со следующей рекуррентной формулой

Хн, = X,., ®    А. (л = 1.2. 3. _.).

где р, q. г— целые константы;

а — двоичное «-битовое целое ч*спо (формирующее матрицу А);

Х„    —«-битовое д воичное целое число;

(X'JX’n.i)*0— двоичное целое число, полученное конкатенацией чисел Х'л и Х*л.,. когда первые («-г) битов взяты из Х„. а последние г битое из (Х,.1)в том же порядке;

А    — матрица размера wx иг. состоящая из нулей и единиц, определенная посредством а;

Х А — произведение, при вычислении которого сначала выполняют операцию X »1. если послед* иий бит X равен 0. а затем, когда последний бит X - 1. вычисляют ХА - (X » 1) © а.

(Здесь Xтакже как и а представляет собой w-мерный вектор, состоящий из нулей и единиц.)

Примечание — Необходимом обьеы памяти для этих вычислений — р слое, период — а эффективность метода Мерсена Твистера выше эффективности метода GFSR. Для улучшения раноомизащы первых (ж — г) битое можно применить следующий ряд преобразований Хг

у := у © (у » и), у := у Ф [(у « а) л 6].

у:=у©[{у«0л^-

у :г у © (у » /).

где б. с— постоянные маски битовдля улучшения рандомизации первых г) битов.

Параметрами этого алгоритма являются (р. q. г. w, а. и. s. t, I, 6. с). Начальными числами являются

Х2.....Хсм и первые (iv-г) битов числах,.

Заключительное значение у является псевдослучайным числом.

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

6.1    Введение

В данном разделе приведено описание методов генерации случайных чисел У. соответствующих различным распределениям, при использовании целых случайных чисел X. соответствующих равномерному распределению. При этом использованы следующие обозначения:

F(y) — функция распределения:

f(y) — функция плотности вероятности непрерывного распределения: р(у) — фумгция дискретного распределения.

6.2    Равномерное распределение

6.2.1    Стандартное равномерное распределение

6.2.1.1    Функция плотности вероятности

1, если 0 й у £ 1 0. если у е [0.1]


6.2.1.2 Метод генерации случайной величины

Если максимальное значение равномерного случайного целого числа X равно (т -1), для генерации стандартных равномерных случайных чисел необходимо применять следующую формулу


Пример—Для всех w-битоеых последовательных целых чисел, генерированных методом, описанным е 5.2 с помощью 5.5. гп = 2.

Примечание 1 — Посхогъку X принимает дискретные значения, величина U также является дискретной.

Примечание 2 — Величдоз U никогда не принимает значения 1 и 0. Велич доз U принимает здию дое 0.0 только, если X = 0. В случае М-последовательности случайных чисел любой метод генерации может выявить эту особенность.

Примечание 3 — Случай-ые числа, соответствующие стандартному равномерному распределено, называют стандартными равномерными случайными числами и обозначают I/,. U2.....Эти числа сдотают

независимым по отношвдою друг к другу.

6.2.2 Общий случай равномерного распределения

6.22.1 Функция плотности вероятности

|1/


1/6. если а £ у й а * 6 0. если у е [а. а + 6]

6.2.22 Метод генерации случайной величины

Если стандартное равномерное случайное число U получено методом, установленным в 6.2.1.2. то равномерное случайное число должно быть получено в соответствии со следующей формулой Y-Ш* а.

6.3 Стандартное бета-распределение

6.3.1 Функция плотности вероятности

Чу)


у 1 у>—. если 0 £ у S1 B(c.d)

0.    если у г [0.1]

1

где B(c.d) = Jxe*,(1-x)rf',<ftr —бета-функция с параметрами си d (с > 0. d>0).

О

6.3.2    Метод Йонка

Если стандартные равномерные случайные числа U-, и U2 независимо генерированы методом, установленным в 6.2.1. то соответствующее стандартному бета-распределению случайное число У получают в соответствии со следующими процедурами.

Если у з U?c ♦ U2a й 1. то У s U,c / У : в противном случае генерируют два новых стандартных

равномерных случайных числа до тех пор. пока неравенство не будет выполнено.

6.3.3    Метод Ченга

Если стандартные равномерные случайные '-мела U, и U2 независимо получены методом, установленным в 6.2.1, то случайное число У. соответствующее стандартному бета-распределению, получают в соответствии со следующей процедурой

minted), если min(c.tf) < 1

а) Я


12ctf-(c+d) 0 ПрОТИВНОМ случае ' v c+tf-2

Ь) Выделяют

V ш -1- ——. W ш cexp(V).

с) Если

(с * d)1n

+

(Стд)У-1п4 t ln(t/ft/2).


тоща

у = <*“хоя*

d) В противном случае генерируют Uf. U2 и переходят к Ь).

Если тах(с. d) £ 1. применяют метод Йонка. в противном случае применяют метод Ченга.

Примечание — Случайныеч«спа. соответствующие бета-рэслределемео. заданному на интервале [а. а + Ь]. получают лтейнмс преобразованием аналопеыо описанному в 6.2.2.2.

6.4 Треугольное распределение

6.4.1 Функция плотности вероятности


-р=—L. если а-Ыуйа + Ь

Ъг

0. если у е [a-b.a + b]

где £> > 0.

6.4.2 Метод генерации случайной величины

Если стандартные равномерные случайные числа и 1^ независимо генерированы методом, уста* новленным в 6.2.1. то случайное число У. подчиняющееся треугольному распределению, определяют по формуле У - а ♦ Ь (U, ♦ U2 - 1).

6.5 Общее экспоненциальное распределение с параметрами положения и масштаба

6.5.1 Функция плотности вероятности

у <а


Ну) - о

о.

где а и £) — параметры положения и масштаба экспоненциального распределения соответственно.

6.5.2 Метод генерации случайной величины

Если стандартное равномерное случайное число U генерировано методом, установленным в 6.2.1. то случайное число, соответствующее экспоненциальному распределемео. получают по формуле

У = -WnfL/) ♦ а.

6.6 Нормальное распределение (распределение Гаусса)

6.6.1 Функция плотности вероятности


где ц и о—среднее и стандартное отклонение нормального распределения соответственно. Примечание — Обычно нормальную спучэжую величину обозначают Z.

6.6.2 Метод Бокса—Мюллера

Ес/ы стандартные равномерные случайные числа I/, и U2 независимо генерированы методом, уста* новленным в 6.2.1. то два независимых нормальных случайных числа Zt. Z2 получают в соответствии со следующей процедурой

Z, = р ♦ о ^-2ln(1-U,)cos{2xU2).

Z2 = р ♦ о 1/-2ln(l-L/,)sm (2xU2).

Примечание 1 — Постольку U, — дискретная ветчина, то Zt. Z2 не подчтяются нормальному распределению е строгом сатсле. Например, используя эту процедуру, верхней границей абсолютах значенм

псевдослучайных стандартных нормальных величин является и = ^ - 2Н\{т~') = ^2Jn m . Таким образом, ест

т = 2Э3. то М * 6.6604, а ест т = (231 - 1). то М <* 6.5555. Отэю, гак как вероятность того, что абсолютте значения случайных величмч истинного стандартного нормального распределения, превышающих М. приблизительно равна Ю’. это редко создает трудности на практике.

Примечание 2 — При получении I/,. U2 линейным конгруэнтным методом последоеагетьно. У, и U2 являются зависимыми, таким образом хвост распределений, полученных Z, и Z2. может существенно отличаться от истинного нормального реелредепетя.

6.7 Гамма-распределение

6.7.1 Функция плотности вероятности

Ну)


—— {{у-е)Я»}с-1вхр{-(у-в)/Ь}. если ука ЬГ(с)

0.    если у<а где а. 6, с— параметры положения, масштаба и формы соответственно.

6.7.2    Методы генерации случайной величины

6.7.2.1 Общие положения

Алгоритмы приведены для трех ситуаций в зависимости от значения параметра формы с.

67.2.2    Алгоритм для с-к (к — целое число)

Используя независимые равномерные случайные числа U,. U2,.... Uk. применяют формулу Y= а - Ып{(1 - У,К1 - U3)... (1 -14».

Примечание — Этим методом для а * 0 и 6 = 2 может быть получено распределение х2 с четным числом степеней свободы.

6.77.3    Алгоритм для с = к * 1/2 (к — целое число)

Используя стандартное нормальное случайное число Zo и равномерные случайные числа Ut. U2.

Uk. применяют формулу

V=a*6[z|/2-ln{(1-^K1-W2)...(1-UJ}].

В случае, когда к-0, член с логарифмом исчезает.

Примечание — Тем же методом при а - О и 6 = 2 может быть получено распределение х2 с нечетным '-мелом степеней свободы

67.2.4    Приближенный метод для с > 1/3

a)    Задают г-с- 1/3. s-Jr. t = г-rin(r). р = 1/(3 Js )и q - - 3 Jr .

b)    Генерируют стандартное нормальное случайное число Z.

c)    Если Z < q. то переходят к Ь).

d)    Вычисляют У = (pZ ♦ s)3. V - Z2/2 и генерируют U.

в) Если (У - tflY -Vi U. выполняют У;= а +6 У (конец).

ОВычюляют W- У-г1п{У)-Г- V.

д)    Если WiU. то выполняют У := а +6У (конец), h) Если W > -Jn(1.0 - U). то переходят к Ь).

Примечание — Метца основан на преобразовании Уилсона—Хилферти. приводящем ^-распределение к прибгыженному стандартному нормальному распределению. Темность такого приближения зависит от значения параметра с. Идея преобразования состоит в следующем: абсолютная разность между процентной л>жой приближенного и точного распределений всегда меньше 07.

6.77.5    Точный метод генерации Ченга для с > 1/2

a) Задаютд=с-1п4иг=с* ^f2c-i.

b)    Генерируют стандартные равномерные случайные числа U, и U2.

c) Вычисляют V- dnl 1 и I. W-c exp(L/,). Zs UfU3.R-q*rV-W.

d)    Если R £ 4.5Z - (1 ♦ In4,5). то вычисляют У = a ♦ bW (выход).

е)    Если R г InZ. то вычисляют У = a ♦ bW (выход).

f) Генерируют стандартные равномерные случайные числа I/, и 1/* и вычисляют

р = Vj2c-\. q = с - 1п4. г - с* J2c -1 .

6.8 Распределение Вейбулла

6.8.1 Функция распределения вероятности

1-ехр

. если у£а


0




Р(У)*

. если у<а

где а. b и с — параметры положения, масштаба и формы соответственно.

6.8.2 Метод генерации случайной величины

Ест стандартные равномерные случайные числа U генерированы методом, установленным в 6.2.1. то случайные числа, соответствующие распределению Вейбулла. получают по формуле

у sa-bOnO-l/)}1*.

6.9 Логнормальное распределение

6.9.1 Функция плотности вероятности


где а и Ь — параметры положения и масштаба соответствующего нормального распределения.

6.9.2 Метод генерации случайной величины

Используя стандартные нормальные случайные числа Z. применяют формулу У - а ♦ exp(OZ)

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

6.10 Логистическое распределение

6.10.1 Функция вероятности

—•• <у <«.


1 + ехрНу-ауЬ)'

(деаиЬ — параметры положения и масштаба соответственно.

6.10.2 Метод генерации случайной величины

Если стандартные равномерные случайные числа U генерированы методом, установленным в 6.2.1. то случайные числа, соответствующие логистическому распределению, получают по формуле


6.11 Многомерное нормальное распределение

Случайные числа У,. У2 У„. соответствующие л-мерному нормальному распределению со средними рьр2.....рл. дисперсиями и ковариациями о4 (1 S /, / £ п). получают, используя взаимно независимые

стандартные нормальн ые случайные числа Z, Z,

У| г Pi +

У2~»2 + a2«Zt ♦ aj22j.

V; = Mn + *„,2, ♦ an2^ ♦ ... + a^Z,,,

гае а„, am — константы, вычисляемые до начала генерации в соответствии с процедурой факторизации Холецкого.

Примечание — в,- (1 £ г. j&n) ковариации, в, — дисперсии У,.

a) Для j-Л au=Jou. а„ = о*/а„ (2£/Sn).

b) Для }-2.....п

t


6.12 Биномиальное распределение

6.12.1    Функция распределения

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

*у)=(к)рЧ1 -рГ^.у=о. 1.....л,

где0 <р< 1.

6.12.2    Методы генерации случайном величины

6.122.1 Общие положения

Рассматриваемые в данном разделе методы позволяют получить случайные числа У. соответствующие биномиальному распределению.

6.1222 Прямой метод

Генерируют л стандартных равномерных случайных чисел U. Искомое число У равно количеству

чисел L/менее р кэ л полу*юммых чисел U.

6.122.3    Метод обратной фушции Вычисляют функцию распределения

F(y)>= ^["^О-рГ*. у = од.... л.

Для получения случайного числа У генерируют стандартное равномерное случайное число U. Случайное число У является наименьшим значением у. для которого U £ F(y).

6.122.4    Метод положения

Вычисляют (л ♦ 1) параметров v0, v,, уйи(л ♦ 1) параметров а,.__а„.

a)    v,= (л + 1)р(у).уг0.1.....л.

b)    Составляют набор индексов G таких, для которых соответствующий параметр v удовлетворяет условию vfai, и набор индексов S. для которых соответствующий параметр у удовлетворяет условию

У„<1.

c)    Для не пустого набора S выполняют операции 1)—4).

1)    Выбирают любой элемент / из G и любой элементу от S.

2)    Устанавливают а( = / и v, = v( - (1 - v,).

3)    Если v, < 1. удаляют элемент /из G и перемещают его в S.

4)    Удаляют элемент j из S.

Если приведенные выше подготовительные действия выполнены, то двухмерное случайное число У получают, выполняя операции d) — f).

d)    Генерируют стандартное равномерное случайное число U и вычисляют V= (л>1 )U.

e)    Вычисляют к = 1у.|и и = V- к. roeLvj— целая часть числа V.

О Если и & V». то У - к: а противном случае У - ак.

6.13    Распределение Пуассона

6.13.1    Функция распределения

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

р(у) = J^J-expHi), у =0.1. 2.....

гдер > 0.

6.13.2    Метод, использующий связь с экспоненциальным распределением

Генерируют стандартные равномерные случайные числа Uv U2.....В качестве У используют макси

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

-ИО-ЦХ1-Ц) ...(1-ия)}<р.

6.13.3    Метод наложения

Сначала выбирают постоянную п. для которой вероятность того, что У > п пренебрежимо мала, например. целая часть числа {р ♦ 6) может быть установлена равной л. Затем применяют процедуру 6.12.2.4. приведенную для биномиального распределения. Однако на сей раз для р(у) должна быть использована функция распределения Пуассона.

Примечание — Этот метоа эффективен, когда р имеет значение от 10 до 100.

6.14    Дискретное равномерное распределение

Для генерации дискретных равномерных случайных чисел от М до N г-битовое двоичное случайное число, полученное в соответствии с рекомендациями 5.1. преобразуют в соответствии со следующими процедурами, где (N - М ♦ 1) не превышает 2'.

a)    Определяют натуральное число к, удовлетворяющее следующему неравенству:

2*’-И 5N-M + 1 52*.

Примечание! — Вегычмча к — наименьшее натуральное число, удовлетворяющее неравенству kitog3(N-M* Ц.

Припер 1 — Если (N- М * 1) = 100, то к = 7. поскольку(2* * 1) = 65s100s27 = 128.

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

Примечание2 — fc-битовое двоичное число Z. Z^Z^Zi.-.Z* соответствует десятичному числу 2*-’Z, + 2^Z2 + 2*-^ + 2*^Z* *... + Zt.

Пример 2 — Если первые 7 битое числа 1011001. то соответствующим десятичным числом является 89(64*16*8*1=89).

c)    Искомое десятичное случайное число — это соответствующее десятичное число плюс (М-1) при отбрасывании чисел более N.

Примечание 3 — Если (N - М * 1) > 2'. то искомое десятник» случайное число мажет быть получено конкатенацией двух игы большего яогычества двоичных случаюых чисел в одно двоичное спучакмое число.

Примечание 4 — При испоп>зовамт лквюйного конгруэнтного метода для генерации псевдослучайных чисел к не должно быть равньш г.

Далее, если (N-M* 1) является десятичным А-значмым натуральным числом и * не является слишком большим, например к меньше 20. может быть использован метод, установленный в 5.2. При этом выполняют процедуру в соответствии с d) и е).

d)    Генерируют последовательность десятичных случайных чисел из к цифр, используя процедуру 5^.

e)    Из последовательности случайных чисел, полученной в соответствии cd). удаляют числа более N. Полученная таким образом последовательность является исхомой последовательностью десятичных случайных чисел.

Приложение А (справочное)

Таблица физических случайных чисел А.1 Таблица случайных чисел

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

Таблица А.1 — Табгмцэ физических случайных чкел

1

93

90

60

02

17

25

89

42

27

41

64

45

08

02

70

42

49

41

55

98

2

34

19

39

65

54

32

14

02

06

84

43

65

97

97

65

05

40

55

65

06

3

27

86

28

07

16

05

18

96

81

69

53

34

79

84

83

44

07

12

00

38

4

95

16

61

89

77

47

14

14

40

87

12

40

15

18

54

89

72

88

59

67

5

50

45

95

10

48

25

29

74

63

48

44

06

18

67

19

90

52

44

05

85

6

11

72

79

70

41

08

85

77

03

32

46

26

83

22

48

61

93

19

98

60

7

19

31

85

29

48

89

59

53

99

46

72

29

49

06

58

65

69

Об

87

09

8

14

58

90

27

73

67

17

08

43

78

71

32

21

97

02

25

27

22

81

74

9

28

04

62

77

82

73

00

73

83

17

27

79

37

13

76

29

90

07

36

47

10

37

43

04

36

86

72

63

43

21

06

10

35

13

61

01

98

23

67

45

21

11

74

47

22

71

36

15

67

41

77

67

40

00

67

24

00

08

98

27

98

56

12

48

85

81

89

45

27

96

41

77

78

24

26

98

03

14

25

73

84

48

28

13

55

81

09

70

17

78

16

54

62

06

50

64

90

30

15

78

60

63

54

56

14

22

18

73

19

32

54

05

18

36

45

87

23

42

43

91

63

50

95

69

09

15

78

29

64

22

97

95

94

54

64

28

34

34

88

96

14

21

38

45

37

87

16

97

51

38

62

95

83

45

12

72

28

70

23

67

04

28

55

20

20

96

57

17

42

91

81

16

52

44

71

99

66

55

16

32

83

27

03

44

93

81

69

58

18

07

84

27

76

18

24

95

78

67

33

45

68

38

56

64

51

10

79

15

46

19

GO

31

55

42

68

53

27

82

07

08

73

09

98

45

72

02

87

79

32

84

20

47

10

36

20

10

48

09

72

35

94

12

94

78

29

14

ВО

77

27

05

67

21

73

63

78

70

96

12

40

36

80

49

23

29

26

69

01

13

39

71

33

17

22

70

65

19

86

11

30

16

23

21

55

04

72

30

01

22

53

24

13

40

63

23

86

37

79

75

97

29

19

00

30

01

22

89

11

84

55

08

40

91

26

61

24

28

00

93

29

59

54

71

77

75

24

10

65

69

15

66

90

47

90

48

80

25

40

74

69

14

01

78

36

13

06

30

79

04

03

28

87

59

85

93

25

73

А-2 Метод генерации физических случайных чисел

Для ген ерши случайных чисел, приведенных в таблице А.1, использован электрический шум диода. В диоде шумовой сигнал достаточно велик вследствие эффекта лавичного нарастания заряда. Поэтому диод часто используют кас источник шума. Был испогъэоеан лавинно-лролепьм диод NC240111. У этого элемента есть источник шума и встроенный усилитесь. ширина полосы частот которого составляет 1 ГГц, а амплитуда — 160 мВ.

Методы преобразования шумового сигнала в цифровую форму.

a)    аналогово-цифровое преобразование:

b)    набподешне последовательности импутъсов с определением кстчества импульсов в едтицу времом:

c)    наблюдение последовательности импульсов с определением интервала времени между последовательными импульсами.

NC2401 — торговая марка продукта, поставляемого Notsecom (жформадея дана только для удобства пользователей настоящего стандарта).

Например, для аналоговоцифрового преобразования может быть использован конвертер OAS-41021’. У этого оборудования разрешающая способность составляет 8 битов с максимальным периодом отбора данных 64 МГц. Данные для приведенной таблицы были отобраны за 1 МГц. Измерение было выполнено с разрешением 3,91 мВ на цифру, и только низший бит был использован для получения случайного числа.

Поскольку у аналогово-цифрового конверсионного оборудования могут появляться ошибочные значеьмя. гистограммы значений после преобразования не показывают равномерного распределения. Для получения богъшвй равномерности распределен*» 2 бита были получены из одного и того же источника случайных чисел

(0.1)    — Случайное число (Rn) = 0.

(1.0)    — Случайное число (Rn) = 1.

(0.0). (1.1) — не использованы.

Случайные члена, приведенные в таблице 1. получены в соспветствны с еыиеупомягутым методом. Есгм вероятности пояеленыя чисел (0.1) и (1.0) равны друг другу, случай-юе число распределено равномерно. Поскогъ-ку нмгервал между последовательными измерениями равен 1 мс. характеристики оборудован*» можно считать постоянными. Поэтому (0.1) и (1,0) считают соответствующими одному и тому же распределению вероятностей. Альтернативный метод корректировки сводится к определению распределения вероятностей характеристик, но постольку распределение зависит от особенностей оборудования, этот метод в ддыюм слуве не был ислогъэо-ван. Далее, для безопасности 32 бита были собраны в одну еамнетвенную группу, или быгы сформированы из псевдослучайных чисел с использованием метода Мерсенна Твистера (обычно называемого genrand). установленного в 5.5. Метод Мерсенма Твистера обычо иницнмруют функцией тА genrand (s). где s = 19660609. Есгм необходимы оригинальные последовательности случайных чисел, они могут быть восстановлен*! с помоиъю единственного ипл повторного использования метода Мерсенна Твистера.

В таблице А.1 приведены десятичные случайные «мела, полученные вышеупомянутым методом, путем отбора высшее четырех бит 32-битоеого представления случайного числа. Если значение этого числа не меньше нуля и не больше девяти, значение используют в качестве случайного числа. Однако, если значение этого чюпа 10 или больше, его отбрэсьеают и генерируют следующее случай оо число.

DAS-4102 — торговая марка продукта, поставляемого Kerthtey Insfruments. Inc. (информация дана только для удобства пользователей нчастояиего стандарта).

Приложение В (справочное)

Алгоритмы генерации псевдослучайных чисел В.1 Текст программы трехпараметричесхого метода GFSR

Ниже природой текст программа на яэысе Си. которая 8 соответствие с ИСО>МЭК 9899 является примером метода GFSR с параметрами (р, q. w) * (1279. 418. 32) и периодом (2,2Г9 - 1). При обрвшемы к фумсции gfsr 0 происходит генерация целого числа из интервала от 0 до (232 - 1) включительно. При обращении к функцме gfsr_31 () происходит генерация целого числа из интервала от О до (231 - 1) включительно. Для обращеме* к функциям gfsr (} и gfsr_31 0 необходима единственная м-ыциагыззция inrt_gfsr (s). Функция пй gfsr (а) выютяет инициализацию при условии, что а качестве начального числа используется 32-битовое целое число без знака [целое число из интервала от 0 до (232 - 1)]. Полученная последовательность обеспечивает 39 независимых серий псевдослучайных чисел, каждая из которых обладает незначительной автокорреляцией, имеет 39-мерное распределение (однородно распределена в 39-мерном гиперкубе) с 32-битовой точностью, и ее функция авто-корреляц»ы такова, что значения близкие к нулю появляются через 21774 ««сел.

Чтобы получтть другую последовательность псееаослучам-ых чисел, необходимо иэма мтъ начальное чс-ло s в фумсции inrt_gfsr (s). В программе могут быть изменены только константы р. q. w. Значение vv должно быть равно 2 в целой степени в соответствие с длиной слова машины. Значение w. в общем случае, равно 32 или 64 в зависимости от возможностей машиш. Например, если длина слова машины 64. постойную w в программе устанавливают равной 64. а функция gfsr () генерирует целые числа из интервала от О до (2е4 — 1) вхлочитепьно. в то время юк фумоаея gfsr_31 () генерирует целые числа из интервала от О до (263 — 1) включительно.

В данной программе предполагается, что длию «беззнакового длинного целого» составляет не меньше 32 бит.

Г................................................

Текст программы грехпараметричесхого GFSR на языке Си

...............................*...............*•/

«define Р 1279 «define 0 418

«define W 32 Г значения W должны быть стопо> ыо 2 V

static unsigned tong state [P] ;

static int statej ;

void init_gfsr (unsigned long s)

{

rti. j. k;

«tatir imognMi inng к [P] :

S &= OxfffffffTUL:

for (i=0 : HP ; i++) { x [i] = s»31 ;

s » 1664525Ш. * s + 1UL : s&=OxfTffffffUL:

)

for (k=0, i=0: i<P: H-+) { state [i[ = CHJL: for{j=0:j<W;j++> { state fij «= 1: state p] И x [k]: xpc) **х((к+0)%Р]; k++:

if (k=P)k = 0:

}

}

statej = 0:

}

unsigned long gfsr (void)

{

int i: unsigned long *р0. *р1 ;

if (state_i >= Р) { state_i = 0; рО = state: pt = state + О ; tor (И): i<(P-Q): r++) *pO+ ** *pl++; pt = state: for (: KP; i++)

•pO+*= *pl++;

>

retwn state [state_H-+J;

}

Л (W-1)-6mto8O0 целое 7 long gfsr_31 (void)

{

return (long) (gfsr() »1);

}

Примечание — Соответствующий текст программы трехпараметрического GPSR на языке BASIC приведен для информации.

OPTION BASEO

REM

DECLARE NUMERIC P

LET P=1279    '«define P 1279

DECLARE NUMERIC Q

LET Q=418    '«define Q 418

DECLARE NUMERIC W

Г значения W догисны быть степенью 2 V LET W=32    !«define W 32

DIM state(P)    Istabc unsigned long state[P]:

DECLARE NUMERIC stalej    Istabc INT state_i;

REM

................•••!

! void init_gfsi(unsigned long s){

!    int i, j, К

!    static unsigned tong    x(PJ:

I    s&= OxfffffiffUL

I    for (1=0; KP; i++) {

I    xfi] - s»31:

!    s = 1664525UL * s + 1UL;

!    s4=0xffflfmUL;

!    }

I    for (k=0. i=0; KP: H-+) {

!    state(i) = OUL;

I    for(f=0;j<W;j++){

!    state(i] «= 1:

!    statefi] |=x(k]:

. P)))    I    x(kj ** x[(k+Q)%PJ;

I    k++:

I    if (k=P) k = 0;


i................................................

FUNCTION nrt_gfsr(s) !

DECLARE NUMERIC 14*

DIM x(P)

LET s = And32(s . MskFjf)

FORi = 0 TO P-1

LET x(i) - SR32U(s . 31)

LET s » Mut32U( 1664525 . s) + 1 LET s = And32(s. MskF_f)

NEXT I LETk=0

FORi = 0 TO P-1 LET stale(i) = 0 FOR H) TOW-1

LET state(i) = SL32U(slate(i). 1)

LET state(i) = Or32(state{i). x(k))

LET x{k) = Xor32(x(V). x (REMAINDERS +

LET k = k + 1

IF k = P THEN LET k = 0

NEXT]

}

state i = 0:


.......I

uns*gned long gfsr(vwd>{ int i;

unsigned long *p0, *p1; i (state.! >= P){ state.i = 0; pO = state: p1 = state +01; for (Hfc K(P-O); i++)


!    "p0++ *= *pi ++;

!    p1 = state:

!    for(: KP; i++)


!    *р0-н+    A= *p1-*-+;

!    )

!    return    siate{state_i++]:

I    }

......"7

! long gfsr_31(voidX

!    retim    (JongHgfsr()»1L

I }


NEXT I

LET state.i = 0 END FUNCTION REM

r.........................................................

FUNCTION gfsr

DECLARE NUMERIC!

DECLARE NUMERIC pO. p1 IF state.i >= P THEN LET stats.i = 0 LET pO = 0 LET p1 = Q1 FOR f=0 TO P-O-1

LET state(pO) = Xor32(state(p0). state(p1» LET pO = pO + 1 LET p1 =P1 + 1 NEXTi LET p1 = 0 FOR F4 TO P-1

LET stste(pO) = Xor32(state(p0) . state(p1)) LET pO = pO + 1 LET pi = P1 + 1 NEXTi END IF

LET gfsr = state(state_i)

LET state.i = state.! + 1 END FUNCTION REM

Г.........................................................

REM /* (W-1)-6i4Toeoe целое 7 FUNCTION gfsr_31 LET gfsr_31 = SR32U(gfsr . 1)

END FUNCTION

В-2 Текст программы пятмпараметрического метода GFSR

Параметры и период датой программы составляют (521. 86. 197. 447, 32) и (2531 - 1). При обращены соответственно к функции gfsr5() происходит генерация целого тела из интервала от 0 до (232 -1) еключитегъ-ми. При иСращепми к функции уЫЗ_31() мритлици! mmipaum цшши чныы nj HHiapaojia ui О ди (211 — 1) включительно. Функция етЛ qfsr5 (s) выполняет инициатзацию при условии, что начагьное число является 32-биговым целым числом без знака (целое тело из интервала от 0 до (232 -1)]. До обращения к функции gfsr5 0 и gfsr5_31 () необходимо выполнить первоначагъную инициацмо init_gfsi5 (s). Полученная поспедоеа-тегъностъ имеет 16-мерное распределение (равномерное распределение в 16-мерном гиперкубе) с 32-битоеой тотостью. а ее функция автокорреляции такова, что период появления близкого к нулю значения составляет 2518.

При необходимости многократного получения наборов случайных тсел для моделирования инициализацию init_gfer5 (s) необходимо выполнить одн* раз перед началом моделирования. После каждого повторения содержанте таблицы х[Р] размера Р и перемог чую state.i необходимо сохранять и использовать их в качестве начальных значений при следующем повторены.

Есть» необходима другая последоватегъностъ с другим периодом, то значентя р, g,. gj и д3 необходимо

выбирать из таблмш 1.

Г.........................................................................—7

Текст программы пяти параметрического GFSR на языке Си

Г............................................................................./


«define Р 521

r OK 02 <03 7


Г W догоою быть степенью 2 7


«define Q1 86 «define 02 197 «define 03 447 «define W 32

Static unsqned long state [P] Д State int state i:

void init_gfsr5 (unsigned long s)

{

inti.j. к:

static unsigned long x (P]; s &= OxfffTffffUL; for (i=0 : KP ; i++) { x [i] = s»31;

s = 1664525UL * s + 1UL ; s&= OxffltfffUL.

}

for (k=0. i=0: i<P: H-+) { state [ij = CKJL : for (j=0; j<W: j++) { state R <<s 1: state p] x (k]:

x [k]    |(k+Q1) %PJ *x [ (k+Q2) %P\ *x ((к+ОЗ) %P]:

k++;

if (k==P) к = 0;

}

}

state_i = 0:

>

unsigned long gfsrS (void)

{

inti:

unsigned long *p0. *p1. ’p2, *p3 ;

й (state_i >= P){ state_i = 0; pO = state; pt = state + Q1: p2 = state + 02 : p3 = state + Q3:

for (i=0; K(P-Q3); i++)

■pu+* ~= 'pm л mp'Z+* " *p3++;

p3 = state:

for (; H4P-Q2): Hf)

*pO++ л= *p1++ * *P2++ A‘p3++: p2 = state:

for(;K(P-Q1);K+)

•p0++ *= *p1++ 4 *p2++ A,p3++: p1 = state: for (: KP; i++)

•p0++    *pl++ A*p2++ л*рЗ++:

}

return state [state_t++];

}

Л (W-1 )-битоеое целое 7 long gfsr5_31 (void)

{

return (long) (gfsrS()»1);

}

Примечание — Соответствующий текст программы пятипарэметричесхого GFSR на языке BASIC приведен для информации.


REM

Текст программ* лятипараметрического GFSR на языке BASIC

*•••/

OPTION BASEO REM

.....t

DECLARE NUMERIC P

LET P = 521

•«define P 512

R£M/*Q1 < 02 < 03 4 DECLARE NUMERIC Q1

LET Q1 =86

•«define Q1 86

DECLARE NUMERIC 02

LET 02 = 197

•«define 02 197

DECLARE NUMERIC 03

LET 03 * 447

•«define Q3 447

DECLARE NUMERIC W

LET W * 32

Г W должно быть степошо 2 */ •«define W 32

DIM state<P)

!static unsigned long stated:

DECLARE NUMERIC state.'

•static int state.i:

REM

•—/

FUNCTION nit gfsfS(s)

!vo*d inct gfsr5funsK3ned long s) {

DECLARE NUMERIC i. j. k

! io* i. i. k;

DIMx(P)

! static unsigned long x{P]:

LET s = And32{s . MskF f)

! s &- OxffffffffUL:

FOR HD TO P-1

! for (я=0: KP: H-*-) {

LET x<i) = SR32U(s .31)

! x[i]» s»31:

LET s = Mul32U( 1664525 . s) ♦ 1

! s = 1664525UL * s + 1UU

LET s = And32{s. MsKF 0

! s&=OxflfflfffUU

NEXT 1

}

LET k=0

FOR f=0 TO P-1

! tor (k=0,i=0: kP; i++) {

I FT = 0

1 data(i| = 01 ■ :

FOR j=0 TOW-1

! tor(pO;j<W:j++){

LET state(i} = SL32U(state(i) . 1)

! statefi] «= 1:

LET state(i) = Or32(stete(i). x(k))

! stateiij И «М;

LET x(k) = Xof32(Xor32(Xor32(x<k)

! xfr) *= x((k+01 )%PIA xl(k+Q2)%P]A

x(REMAiNDER(k + Q1. P))>

4(k+Q3J%Pt

x(REMAJNDER(k + 02. P))} x(REMA»NDER(k + 03. P)))

LET k *k + 1

! к-м-:

IF k = P THEN LET K = 0

! if (k==P) k = 0:

NEXT]

}

NEXT I

)

LET state i = 0

! state i = 0;

END FUNCTION

!>

REM

.....i

FUNCTION gfsr5

(unsigned long gfsr5(void) {

DECLARE NUMERIC I

! inti;

DECLARE NUMERIC pO. pi. p2. p3

! unsigned long *pO. *p1. "p2. *p3

IF state.i >= P THEN

! Я (state.i >=P){

LET state i = 0    ! state i = 0:

LET рО = 0 LET р1 - Q1 LET р2 = Q2 LET рЗ = Q3 FOR i=0 ТО P-Q3-1

LET state(pO) = Xor32(Xor32(Xor32(state(p0) state(p1)). state(p2)). state(p3))

LET pO = pO + 1 LET p1 * pi + 1 LET p2 = p2 + 1 LET p3 * p3 + 1 NEXTi LET рЗ = 0 FOR N TO P-Q2-1

LET stste(pO) = Xor32(Xor32{Xor32(8tale(p0) . state(p1)). stale(p2)). state(p3))

LET pO = pO + 1 LET p1 * pi + 1 LET p2 = p2 + 1 LET рЗ * p3 + 1 NEXTi LET p2 = 0 FOR N TO P-Q1-1

LET state{pO) = Xor32(Xor32{Xor32(state(p0> state{p1)). state(p2)). state(p3))

LET pO = pO + 1 LET p1 = p1 + 1 LET p2 = p2 + 1 LET рЗ * p3 + 1 NEXTi LET p1 = 0 FOR N TO P-1

LET statetpO) = Xor32(Xor32(Xor32(state(p0)

«4ade(p1 J) etatefp?)) , etafe(p3))

LET pO = pO + 1 LET p1 = p1 + 1 LET p2 = p2 + 1 LET p3 = p3 + 1 NEXTi END F

LET gfsrS = state(statej)

LET state_i = state_i + 1 END FUNCTION REM

/.....................................................*.....

REM /* (W-1 )-битоеое целое 7 FUNCTION gfsr5_31

LET ^f5_31 - SR32U(gfsrS . 1)

ЕЮ) FUNCTION


pO = state: pi = state + Q1; p2 = state * 02; p3 = state + Q3; FOR 0=0: i<(P-Q3): r++)


j    *pO++ A= *p1++ * *p2++    A*p3++;

!    p3 = state:

!    far (; i<(P-Q2): i++)


j    *pO++ A= *p1++ A *p2++ A*p3++;

!    p2 = state:

!    far (: i<(P-Q1); i++)


l    *pQ++ A= *p1++    A *p2++ A*p3++;

!    p1 = state:

!    far (; KP-. i++)


!    *pO++ A= *p1++ * *p2++ A*p3++;

! }

! return state(state_i++]:

!)


•'7

•long gfsr5_31(vorf> {

1 return (longXgtsr5()»1);

!}


B.3 Текст программы комбинированного метода Таусеорта

Ниже приведен текст программы комбинированного метода Таусеорта на языке Си. генерирующего цегью числа из м-гтереала от 0 до (231 - 1) вюочитетъно. на основе комбинации трех последоватетъностей параметров Таусеорта (31.13. 12). (29. 2.4) и (28. 3.17).

Иющиапизэщся irvt_taus88 (S) происходит при условии, что нэчагьное число s является 32-битовым це/ым числом без знака [целое число из интервала от 0 до (2й - 1) вхлючттегъно). Для получения другой последоватетъ-ности псеедослу гак ых чисел необходимо измст чтъ нэча/ъное «мело s. Перед обращением к taus88_31 ( } необ-


ходимо одны раз выполнить инициализацию init_taus88 (s). Инициализация может быть выполнена без испогъ-эоеания функции irat_taus88 (s) с помощью выбора подходящих качений s,. и Sy Однако дпя инижзлиззи>и должны быть выпогмены следующие три условия:

•    хотя бы один разряд из высших 31 разряда а, равен едиютце;

•    хотя бы один разряд из высших 29 разрядов 5? равен едммце:

•    хотя бы один разряд из высших 28 разрядов Sj равен едю-мце.

Поаюлысу сэ»ый низимй разряд s*. три низших разряда $2 и четыре ьызших разряда S3 проигнорировав, полученная последовательность случакых чисел не зависит от кэмененны в этих разрядах. В данной программе предполагается, что длина «беззнакового длинного целого числа» составляет 32 бита (разряда).

г.............................................................................I

Техет программы комбинирооа! ■ юго метода Таусворта на языке Си

Г............................................................................./

stabc unsigned long s1. s2. s3. b ;

void init_taus88 (unsigned long s)

{

inti:

unsigned long x [3]:

f=0;

vrfiie 0<3) {

(f(s&0xfmm0UL){

x[i|ss:

»++;

}

s = 1664525UL ' s + 1UL:

>

s1 =x[0):s2 = x(1):s3 = x(2]:

}

Г 31-битоеое целое V

long taus88_31 (void)

{

b = <((s1 « 13) * s1)» 19):

Sl = (((Sl 4 4294967294UL) ««. 12) 'O) ;

b = <((s2 « 2) * s2)» 25);

s2 = (<(s2 & 4294967288UL) « 4) *t>):

b = ({(s3« 3)A s3)» 11):

s3 = («S3 & 4294967280OL) «17) *b):

return (long) ((si * s2 * s3) »1):

}

В этой программе операторы b * (((s1« 13)* s1)» 19). s1 = (((s1 & 4294967294UL) « 12) *b)

генерируют ч«спа в последовательности Таусворта с параметрами (31, 13. 12) в s,. а операторы b * (<(s2 « 2) * s2) » 25). s2 = <((s2 & 4294967288UL) « 4} *b) и

b = «(s3«3) *s3)>> 11):

s3 = (((s3 & 4294967280UL) « 17) *b)

генерируют чтела последовательности Таусворта с параметрами (29. 2. 4) и (28. 3. 17). Sj и £3 соответственно. Три двоичных целых -мела (р. q. f) объеднмяют с помощью побитовой операции «источающее ИЛИ» и 31-битоеая последовательность псевдослучайного числа получена.

Выбор трех параметров (р, q. Q позволяет полу^мть лучшее многомерное равномерное распределение последовательности псевдослучайных чисел после операции объединения. Значения параметров необходимо сохранять. Чтобы получить другую последовательность псевдослучайных чисел, необходимо изменмть начальное число.

Ест необходимо получить неэаеисимьы набор случайных тсел для каждого повтор» мл моделирования, функцию инициалкзаиmi init_taus88 (s) необходимо вызвать одт раз в начале моделирования. После каждого повторения значения st, Sj и S3 необходимо сохранять и присваивать переменным s,. Sj и *з соответственно, как начальные значения при следующем повтор» ми.

Примечание — Соответствующий текст программы метода Таусворта на языке BASIC приведен для информации.

REM ..................................*.................*................—Ч

REM Текст про грамма для метода Таусворта на языке BASIC

REM ..................................................*....................../

OPTION BASE 0 REM

void trat_taus86(uns*gned long s) ( inti:

unsigned long x[3); i=0: white (КЗ) {

if(sSOxfmfffOUL) {

x[i] = s: K+;

}

s = 1664525UL ’ s +1UL;

}


/................*.............................

FUNCTION init_taus88<s)

DECLARE NUMERIC I

DlMx(3)

FOR i = 0 TO 2

IF And32(S . MskF_0) о 0 THEN LET x(i) = s END IF

LET s = Mii32U<1664525. s) + 1 NEXT I LET s1 = x(0)

LET s2 = x{1)

! s1 = x[0]; s2 = x( 1); s3 = x[2];

О

Hong taus88_int(void>

{

! b = («s1«13)As1)»19);

! Si = {<(s1 44294967294) « 12) * b);

! b = (((s2 « 2) * s2) » 25);

! s2 = {«s2 44294967288) « 4)A b);

! b = (((S3 « 3) A S3)» 11);

! s3 = ({(S3 44294967280) « 17) A b);

! refcxn (longX(s1 A s2 A s3)» 1):

!}


LET s3 = x{2)

EM) FUNCTION REM

FUNCTION laus86_31

REM /**”* 31-битовое целое —••/

LET b - SR32U(Xor32(SL32U<s1. 13). s1). 19 LET s1 = Xor32(SL32U(And32(s1 . MskF.e).

12). b)

LET b - SR32U(Xor32(SL32U(s2. 2\. s2). 25)

LET s2 = Xor32(SL32U(And32(a2 . MsfcF.B).

4). b)

LET b - SR32U(Xor32(SL32U(s3. 3). s3). 11 LET s3 = Xor32(SL32U(And32(s3 . Ms*F_0).

17). b)

LET Iaus88_31 = SR32U(Xor32(Xor32(s1. s2). s3>. 1)

END FUNCTION

8.4 Текст программы для метода Мерсенма Теистера

Ниже приведен текст программы для метода Мерсенна Теистера на языке Си. Функция gen rand () генерирует псевдослучайные тела е виде целого 32-битового числа без знака из ттереала от 0 до (232 - 1} вхпочительно. Фужция genrand_31 0 генерирует псевдослучайные числа в виде целого 31-бигового числа без знака из интервала от 0 до (231 - 1) включительно. Функция inl_genrand (s) инициализирует начальное число в виде 32-битоеого целого числа без мака [целое число из интервала от О до (232 - 1) включительно). Перед обращением к genrand 0 или genrand_31 () необходимо один раз выполнить инициатзацию ю< genrand (s). Различные начальные числа s приводят к генеращм разных последовательностей случамгых чисел. Параметры в этой программе необходимо сохранять.

Если необходимо полутть независимый набор случайных чисел в каждом из многократных повторений при модетроеании. к функции инициатзацт init_genrand (s) следует обращаться только один раз перед началом моделирования После каждого повторения содержимое тэбтцы размера Р и значение переметой тб должны быть сохранены и использованы кас начальные значения при следующем повторении.

Пример — В денном примере использовано р = 624 слове с параметрами (624. 397, 31, 32, 0x9908b0df, 11, 7. 15, 18, 0x9d2c5680, 0xefc60000). Здесь числа из 10 зненов, начинающиеся с Ох. являются 32-6итовьши целыми без знака, представленными в шестнадцатеричном коде. Период равен (21**37 -1), а числа распределены равномерно в 623-размерном гиперкубе с 32-битовой точностью. Кроме того последовательность соответствует равномерному распределению в 3 115 мориом пространстве с 6-битовой точностью.

В датой программе длина «беззнакового длинного целого» составляет не менее 32 бит.

Текст программы метода Мерсенна Тоне тора на язьке Си ...........................*....................../

Л Параметры периода’/

«define Р 624 «define Q 397

«define MATRIX.A 0x9908b0dfUL «define UPPER MASK 0x80000000UL «define LOWER MASK 0x7ffffTTfUL


Г постоянный вектор a 7 Л наиболее значимые (w-r) бит V Г последние значимые г бит V


stabc unsigned long тп( [Р] ;    Г массив состояния векторе*/

static ini mb=P+1 ;    Г mb==P+1 ояачаег. что mt [PJ не

инициализирован •/

Г инициаткзация mt (Р] с начальным значением а */ void mit genrand (tmsigned long s}

{

mt [0] = s & OxfffffffTUL ;

for (mti=1 : mti<P ; m6++) {

mt [mb'] = (1664525UL * mt (mtH] + 1UL) ;

mt [mb'} &= OxffffffffUL:

)

}

Л генерация случайного числа на интереалв(0. Oxffffffff] */ unsigned long genrand (void)

{

unsigned tong у ;

stabc unsigned tong mag01 [2] = {OxOUL MATRIX.A};

Г mag01 [x] = x* MATRIX.A для x=0. i V

4 (mti »«Г) {    Г генерация Г слое одиюерсмс1ию V

intkk:

Л (mti == Р+1) init_genrand (5489UL) ;


Г если init .genrand ( } не вызвано */

Г использовано не подходящее начальное значение*/

for (kk=0 ; kk<P-Q : kk++) {

у * (mt [kkj AUPPER.MASK) | (mt [kk+1J 4LOWER.MASK): mt [kk] = mt (kk+Q) * (y » 1) * mag01 [y & 0x1Uq:

}

for(; kk<P-1: kk++){

у »(mt [kk] &UPPER.MASK) | (mt [kk+1} &LOWER.MASK): mt (kk] = mt [kk+ (Q-P) ] * (y » 1)A mag01 (y & 0x1UL];

}

у = (mt [P-1J &UPPER.MASK) \ (mt [0] 4LOWER.MASK); mt IP-1] = mt (Q-1JA (y » 1) * mag01 (y & 0x1UL]:

mti = 0:

}

у = mt [mti++]

Г Темперирование */


,*=^>>11);

У А= (у « 7) & 0x9d2c56B0UL . у *ж <у « 15) & Oxefc60000UL ; у** {у» 18):

гейет у:

}

Г генерация случэююго числа из жтереала {О. 0x7fffffff] V

long genrand_31 (void)

{

retun (long) (genrand( ) »1);

}

Примечание — Соответствующий текст программы метода Мерсенна Таистера на языке BASIC приведен для информации

REM /...............*..................................../

REM Текст программы для метода Мерсенна Теистера на языке BASIC

OPTION BASE 0

DECLARE NUMERIC UPPER.MASK LET UPPER.MASK = BVALf800000«r . 16)


REM

/...........................................

REM Г Параметры периода 7 DECLARE NUMERIC Р LET Р = 624 DECLARE NUMERIC О LET Q = 397

DECLARE NUMERIC MATRJX.A LET MATR1X.A = BVAL(«9908b0df> . 16)


......./

Wdefirte P 624 IfWefine Q 397

•Mefine MATRIX.A 0x9908b0dfUL Г постоянный вектор a У

liWefine UPPER.MASK Ox80000000UL Г наиболее значимые w-г бит У


ПРС1 ARF N1 IMFRir I OWFR.MA4K

LET LOWER.MASK = BVALf*7Wffll*. 16)    !*Jefine LOWER.MASK 0x7fflfflfUL

Г последние 3hj иные г бит V

DIM mt(P)

DECLARE NUMERIC rrrti LET mb = P + 1


REM

/...............................................................

REM Г юидиализаиия mt[P] с начальным значением У FUNCTION init_genrand(s)

LET mt(0) = And32(s . MskF.f)

FOR mb * 1 TO P - 1


Istabc unsigned long mt(P];

Г массив состояния вектора */

Istabc int mb«P+1;

Г mb==P+1 означает что mtpj не инициализирован У

■•••—•у

Noid irrit_genrand(unsigned long s) { *    ml[0]= s & OxfffffWUL;

! lor (mb*1; mb<P. mti++){

LET mt(mb) = Mul32LH166452S . mt(mti-1)) + 1


LET ml(mti) = And32(mt(mb). MskF.f) NEXT mb END FUNCTION


Г тфпЬ] = (1664525UL * mt(mb-1] + 1LR_); ! mtfmti] &= OxfffffffTUL:

! }

!}


REM

/.....


у = {mt[kkl &UPPER.MASK) | (mt (kk+1J &LOWER.MASK):


Г mt(kk] = mtJkk+Q)A (y>> 1) A mag01 [y &0x1UL];

!}

» for (*k<P-1;kk++){

! у * (ml [kk] & UPPER.MASK) | (mt[kk+1J &LOWER.MASK):

! mt(kk] = mt(kk+(Q-P)] *(y » 1) * mag01[y & 0x1UL]:

!>

(у = (mt[P-1J & UPPER.MASK)! (mtlOJ&LOWER.MASK):

(m*P-1] = mt(Q-1j * (y » 1) * magOI (y&0x1UL}:

! mt » 0;

!}

! у = mt[m6++J:

! У *=<У »11):

(у *= (у « 7) & 0x9d2c5680UL;

(у ** (у « 15) & Oxefc60000UL,

(у*=(У»1в):

! return у.

!}


......../

(tong genrand_31 (void) {

( return (tongXgenrand()»1): !}


REM Г генерация случайного тела из жтереала [O.OxffffRR] V FUNCTION georand DECLARE NUMERIC у D4M mag01(2)

LET mag01(0) = 0

LET mag01(1) = MATRIX.A


! unsigned long genrand(void) { ! wsigned tong y:


IF mti >= P THEN

DECLARE NUMERIC kk IF mti = P + 1 THEN


LET у = mit_genrand(5489)

Г использована ошибочная инициа/мззция S7 END IF

FOR kk=0 TO P-Q-1


(static unsigned tong mag01 [2}=^0x0UL. MATRIX.A}:

Г mag0t|xj = x • MATRIX.A for x=0.1 V NT (mti >= P){

Г генерадэв» P слов одновременно V 'rtkk;

(i (mti == P+1)

Г если inA_genrand() не вызван V ! nt_genrand(5489UL);


(    lor(kk=0*k<P-Q:kk++){


LET у = Xor32(And32(mt(kk). UPPER.MASK). And32(mt(Wc+1). LOWER.MASK)}

LET mt(kk) = Xor32(Xor32{mt(kk+Q). SR32U(y . 1)). mag01(And32(y . 1)))

NEXT kk

FOR kk=kk TO P-2

LET у = Xor32(And32(mt(kk). UPPER_MASK). And32(mt(kfc+1). LOWER.MASK))

LET mt(kk) = Xor32(Xor32(mt(kk+Q-P) SR32U(y . 1)). mag01(And32(y . 1)))

NEXT kk

LET у = Xor32(And32(mt(P-1) . UPPER.MASK). And32(mt(0). LOWER.MASK))

LET m*P-1)    =    Xor32{Xor32(mt(Q-1).

SR32U(y .1)). mag01(And32(y . 1)»

LET mti = 0 END IF

I FT у = тЦптЬ)

LET mti = mb + 1

REM Г Темперирооа че */

LET у = Хог32(у. SR32U(y. 11))

LET у = Xor32(y . And32(SL32U(y. 7). BVALT9d2c5680" . 1в)))

LET у = Xor32(y. And32(SL32U(y .15). BVALTefc6000Cr. 16)))

LET у = Xor32(y. SR32U(y. 18))

LET genrand = у END FUNCTION REM

Г...............................................*.....................

REM Г генерация случайного тела из интервала (0.0x7fW(fQ */ FUNCTION genrand_31

LET genrand_31 = SR32U(genrand . 1)

END FUNCTION

B.5 Линей и ьм конгруэнтный метод В.5.1 Общие положения В.5.1.1 Применение

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

В.5.1-2 Определение

Большая часть линетых конгруэнтных методов генерирует последовательности псевдослучайных чисел

X,. Х2.....ислогъэуя следующее рекуррентное соогноиихыо

Х„ = mod (аХл, + с. гл) л * 1. 2.__

где вил — положительные целые числа, с — неотрицательное целое число.

Линейный юдоруэнгный метод определен, как тогысо заданы знача ыя параметров a. m и с. Кроме того, если задано начальное число Х0. полученная последовательность чисел однозначно определена.

Примечание 1 — Алгоритм рекуррентных соотношемгй состоит а следующем. Вычисляот(аХ0 + с), используя начальное число Хо. делят результат на m и определяют остаток от деления X,. Затем вычисляют (aXf + с), делят результат на гл и определяют остаток от деления Х2. Эту процедуру повторяют столько раз. сколько необходимо.

Примечание 2 — Значение л. для которого X, = Х0 в первый раз. называют периодом последоватегъ-

В.5.1.3 Метод выбора эначений параметров

Значения а. т и с не могут быть определены произвольно. Они должны быть выбраны следующим образом.

Поскольку т является верхним пределом периода последовательности чисел, полученной линейным конгруэнтным методом, мачете т должно быть установлено как можно богъше. Спеоовзтегъно. при испольэоаа-мм. например. 32-битовых компьютеров, рекомендуется устанавливать т = 232 иш m * 231 - 1.

Для выбора с нет строгого критерия. Однако период полученной последоватегъносги зависит от того равно с нулю иты положительному целому телу.

Для множителя а должно быть установлено значение, которое обеспечивает хорошие результаты в комбинации с выбранньмы значениями тис (сы. таблицу 8.1).

Примечание — В случае, когда т равно 2 а целой степени и с равно 0. период не превышает mf4. Есгм с — нечетное число, период равен т.

В.5.1.4 Пример параметров

Для 32-битоеых комгъютерое следует использовать один из наборов параметров, приведенных в табшце В.1.

Таблица В.1 — Наборы параметров для нспогьэоеания шлейного яхруэнтного метода

Номер строи

А

С

м

1

1 664 525

2

1 566 083 941

0

3

48 828 125

0

232

4

2 100 005 341

0

231 - 1

5

397 204 094

0

23' -1

6

314 159 369

0

23’ - 1

Примечание 1 — Символ * указывает, что может быть испогъэовэно гвобое нечетное число.

Примечание 2 — Испогъэование параметров, приведенных в первой строке, обеслечюавт генерацию целых чисел из жтервала от 0 до (232 - 1).

Примечание 3 — Испогъэование параметров, приведенных во второй или третьей строках, обеспечивает генврвцмо чисел вида (4/ + 1) для i = 0.1.....(2м- 1). или (4г + 3) для / = 0.1.....(2м-1) в зависимости

от начального числа Xо-

Примечание 4 — Испогъэование параметров, приведенных е строках 4. 5 и б. обеспечивает генерацию пегожитегъных целых чисел из интервала от 1 до (211 - 2).

Примечание 5 — Следует испогъэоеать более высокие разряды генерированных случайных чисел, а тзкие разряды не следует использовать.

В.52 Текст программы для линейного конгруэнтного метода В.5.2.1 Общие положения

Ниже приведен текст программы для линейного конгруэнтного метода на языке Си. Программа соответствует ИСОМЭК 9699. Приведено два варианта программы, одт — для случая, когда т = 232. другой — для случая, когда т = (231 - 1). Эти варианты соответствуют рекомендациям В.5.1.

В.522 Вариант т = 232

При каждом обращемы функдея kong32 () формирует случайное целое число от нуля до (2“ - 1) вкпкпм-тельно. Рвзутътат имеет тип «длинного целого числа без знака*. При каждом обращен*» функция lcoog32_310 формирует случай юо целое число от нуля до (231 - 1) включительно. Результат имеет тип «дптного целого числа». Функция инициализации init_lcong32 {использующая длинное начальное целое без знака) выполняет м-мциагызацию так. чтобы неотрицательное целое число типа «длинное целое без знака» было установлено как начальное число. Есгм второе слагаемое с = 0 и исходное начальное число Х0' является нечетным, то Xq монет быть установлено как Xq = Xq\ Однако, есгм задано четное исходное начальное ч*сло Xq". в случае с = 0 для получения печального числа Xj к исходному нагельному чюлу прибавляют единицу Xq = Х0' + 1. В других случаях используют в качестве Xq начальное число гпофХд": /л).

Множитель и второе слагаемое изменяются при изменен*» значений MULTIPLIER и INCREMENT в каждой программе. Последоеателыюсть случайных чюрл перезапускается при иаюльэооами выхода 1сопд32 () в качестве аргумента фужции ижцмапизэции init_icong32 (начальное число).

В.5.2.3 Вариант ш = 231 - 1

Каждый раз при обращении к функщм 1сопд31 () она форьмрувт случайное целое '-мело из интервала от 1 до (231 — 2) вкпочнвгъно. Результат и моет тип «дгьмюго целого числа». Функция инициализации init_lcong31 (использующая дгьнюе целое начаты юо число без мака) устанавливает в качестве начапного числа неотрицательное целое число. Кж и е таблызе В.1. второе слагаемое с всегда равно 0. Поэтому начальное «мело Xq на должно быть равно 0. Однако, если Xq' = 0. в качестве Xq испогъзуют специальное число (19 660 809). В других случаях в качестве Х^ испогъзуют mod(X^*; ш).

Для изменений знакимй множителя необходимо его указать е операторе присвоения константе MULTIPLIER в тексте программы.

........................................................../

Текст программы лдойного коыруэнтмого метода на языке Си ................................*......................../

Часть 1. Modulus = 2*32

«define MULTIPLIER 1664525UL «define INCREMENT 1UL

State unsigned long state32 :

Unsigned tong lcong32( vwd )

{

state32 = ( state32 * MULTIPLIER + INCREMENT ) & OxFFFFFFFFUL; natnm «tata.12'

}

tong lcong32_31( void )

{

state32 = (state32 * MULTIPLIER + INCREMENT ) & OxFFFFFFFFUL; return state32»1;

}

void inrt_lcong32(iXTsigr>ed long s)

{

Г начальное «мело должно быть нечетным, есгм слагаемое INCREMENT равно 0 V if ((INCREMENTS) && (s%2 == 0) X s++;

)

state32 = s:

}

Г...............................*.....*........*.........

Часть 2. Modulus = 2*31-1 = 2147483647

.................*.........*............................../

«undef MULTIPLIER «uxfer INCREMENT «urxfef NBfT «define NBIT 15 «define MASK ((1«МВП>1)

«define MASK2 ((1 <<2*NBIT) -1)

«define MULTIPLIER 2100005341UL «define MULTIPLI ER_LO (MULTIPLIER & MASK) «define MULTIPLIER.HI (MULTIPLIER » NBIT) Static imsigned long state3l :

long lcong31 ( void )

{

unsigned long xlo. xhi; unsigned long zO. z1. z2 ;

xlo » stste31 & MASK; xhi = state31 » NBIT :

zO = xlo ‘ MULTFUER_LO.    Г 15bit * 15Ы *> 30Ы V

z1 = xlo * MULTJPUER_HI+ xhi * MULTIPUER.LO ;

Г 15bit1 16W * 2 => 32bit V

z2 = xhi * MULTTPUER_HI:    Г 16bit * 16Ъй *> 32M V

zO += (z1 & MASK)« NBIT:

z2 +* (z1 » NBIT) + (zO »(2*NBIT));

z0s(z0& MASK2) | ((z2&1) « (2'NBIT)};

z2 »=1:

state31 * zO + z2 :

if (state31 >=Ox7fffTfffUL) state31 -= 0x7fffffffUL .

Г Это «мело не должно превышать 2*0x7flffffTUL V return (long) state31 :

}

void init_icong31 (unsigned long s)

{

i ( s == OUL ) s=19660609UL :    Г земельное чтсло не должно быть 0 7

s * S % 0x7fflfHfUL ; state31 = s:

}

Примечание! — Текст программы для линейного «х-груэнтного метода на языхе Basic приоодоп для информации.

REM /.........................................................

RCM Программные коды лилейного конгруэнтного метода на им» BASIC

REM

REM /...............................*.........................

REM Часть 1. MotMus = 2A32

OPTION BASEO REM

DECLARE NUMERIC MULTIPLIER

LET MULTIPLIER = 1664525    ««define MULTIPLIER 1664525UL

DECLARE NUMERIC INCREMENT

LET INCREMENT = 1    '«define INCREMENT 1UL

Istatic unsigned long state32:

lirtsjgned long lcong32u( void )    {

' state32 = ( state32 ’ MULTIPLIER + INCREMENT) & OxFFFFFFFFUL:

! return state32:

0


DECLARE NUMERIC state32 REM

FUNCTION lcong32

LET state32 = And32«state32 * MULTIPLIER) INCREMENT. MskF_f)

LET lcong32 = state32 END FUNCTION REM

FUNCTION init_lcong32(s)    (void init_toong32(insigned long s) {

REM /* начальное число должно быть нечетным, если слагаемое INCREMENT равно 0 V F (INCREMENT = О) AND (REMAINDERS. 2) = 0)    ! if ((INCREMENT**©) && (s%2 — 0)) {

THEN

LET s » s + 1    ! s++;

? }

! state32 = s: !}


FUNCTION lcong32_31


LET lcong32_31 = SR32U(tcong32 . 1) END FUNCTION REM

/”...........................................


Hong lcong32( void )    {

! state32 - ( state32 * MULTIPUER ♦INCREMENT) & OxFFFFFFFFUL: ! return state32»1:

9

......./


END IF

LET state32 = s EM) FUNCTION

REM /....................*..........*.........................

REM Текст программы линетого конгруэнтного метопа на языке BASIC REM ....................*.........*........................./

REM

REM /.........................................*...............

REM Часть 2. ModUus = 2*31-1 = 2147483647

REM ..............................*.........................../

OPTION BASEO

LET z1 = z1 + xhi * MULTIPLIER LO LET z2 = xhi' MLILTIPLIER.Hi

LET zO = zO + SL32U(And32(z1 .MASK).NBIT)

LET z2 * z2 + SR32U(z1 . NBIT) + SR32U(zO. 2 * NBIT)


DECLARE NUMERIC NBIT LET NBJT = 15 DECLARE NUMERIC MASK LET MASK = SL32U<1 . NBIT) - 1 DECLARE NUMERIC MASK2 LET MASK2 = SL32U(1.2'NBIT) - 1

DECLARE NUMERIC MULTIPLIER LET MULTIPLIER = 2100005341 DECLARE NUMERIC MULTIPUER.LO LET MULTIPUER.LO = And32 (MULTIPLIER. MASK)

DECLARE NUMERIC MULTIPUER.HJ

LET MULTIPLIER.»! = SR32U(MULTIPUER .

NBIT)

DECLARE NUMERIC state31

REM /.....................*.....................

FUNCTION lcong31

DECLARE NUMERIC xk>. xN DECLARE NUMERIC z0.z1.z2 LET xlo = And32(state31 . MASK)

LET xN = SR32U(state31 . NBIT)

LET zO * xlo * MULTIPUER.LO

LET z1 =xto* MULTIPLIER HI

«define NBIT 15 ! «define MASK ((1«NBIT)-1)

! «define MASK2 {(1«(rNBlT)}-1> ! «define MULTIPLIER 2100005341UL

> «define MULTIPUER.LO (MULTIPLIERS MASK)

l «define MULTIPUER.HI (MULTIPLIER» NBIT)

(static unsigned long state31:

............./

Hong tcong31( void ) {

! insigned long xlo. xhi;

! unsigned long zO, zl. z2;

! xlo = state31 & MASK:    //1stval:9

(xhi« state31 » NBIT. //1stval:600 ! zO = xlo * MULTI PLIER.LO;

Г156Й * 1564 => ЗОЫ V ! z1 = xlo ’ MULTIPUER.HI + xhi * MULTTPLIER.LO.

! Л15ЬЙ ’ 166it * 2 => 32bit V ! z2 = xhi ‘ MULTI PLIER.HI;

Г 1664* 1664 => 3264 '/

! zO += (z1 & MASK)« NBIT:

//1st val:897833157 I z2 += (z1 » NBIT) + (zO »(2*NBIT));

LET zO = Or32(And32(zO . MASK2). SL32U{And32<z2.1). 2 * NB1T))

LET z2 = SR32LKZ2.1)


! zO s (zO & MASK2) | ((z2&1) «(2*NBIT));

!z2»=1:


LET state31 = zO + z2

REM Г Эго число не должно быть более 2*0x7fnffFfUL V F state31 >= 2147483647 THEN LET state31 = state31 - 214748Э647 LET !cong31 = state31 END FUNCTION REM

/................................................*.............


!state31 = zO z2;

! IF (state31>=0x7ffffflflJL) state31-= 0x71TfffffUU

! return (long) state31:

0

......4


FUNCTION init_lcong31(S)

REM ! Г начальное число не должно быть 0 */ IF s = 0 THEN LET s » 19660809 LET s = REMAINDERS . 2147483647)

LET state31 = s EM) FUNCTION


(void init_lcong31(ixisigned long s) {

! *<s —0UL)s=19660809UL ! s = s % 0x7fffffffUL.

! state31 = s

0


Примечание2 — Приведенный токе текст программы на языке BASIC необходим для преобразования программных кодов языка Си в программные коды языка BASIC, преобразования случайных чисел в соответствт с приложением А и вьгалнения побитовых операдой на языке BASIC.

REM /.....*.......................................

REM Программные коды функций на языке BASIC REM ............................................./


ОРТКЖ BASE 0

REM /..................................................../


DECLARE NUMERIC MskF f DECLARE NUMERIC MskF.e DECLARE NUMERIC MskF 8 DECLARE NUMERIC MskF 0


LET MskFJ = BVAL(«ffmm» . 16)

LET MskF_e = BVAL<«*fflfe» . 18)

LET MskF_8 = BVAM«WW8» . 16)

LET MskF_0 = BVAL<«MfffO* . 16)

REM /.........................................../

FUNCTION Or32(xAjcB)

DECLARE NUMERIC Ori, OrC


LET OrC = 0 FOROri=0TO31 LET xA= xA/2 LET xB = xB/2

IF (INT(xA) <> xA) OR (INT(xB) о xB) THEN LET OrC * OrC + 2 A Ori END IF

LET xA= INT(xA)

LET xB = INT(xB)

IF (xA = 0) AND (xB = 0) THEN EXIT FOR NEXT Ori LET Or32 = OrC END FUNCnON

REM /....................*....................../


FUNCTION And32(xAjcB)

DECLARE NUMERIC Andi. AC LET AC = 0 IF xA > MskF_f Tl-EN

LET xA * xA - INT(xA i 4294967296) * 4294967296 END IF

IF xB > MskF_f THEN

LET xB = xB - HT(xB / 4294967296) * 4294967296 END IF

IF (xA = 0) OR (xB = 0) THEN LET And32 = 0

ELSEIF xS = MskF f THEN    !&HfflR!fr

LET And32 = xA

ELSEIF xA= MskF fTHEN LET Алй32 = xB

ELSEIF xB = MskF 8 THEN    !&Н1ГШ8

LET And32 = !NT(xA / 8) * 8

ELSEIF xA » MskF_8 THEN    !&Н1ГШ8

LET And32 = INT(xB / 8)' 8

ELSEIF xS = MskF_0 THEN    !&HfRffflO

LET And32 = INT(xA / 18) * 16

ELSEIF xA = MskF OTHEN

LET And32 = INT(xB /16) * 16 ELSE

FOR Andis0 TO 31 LET xA = xA/2 LET xB = xB/2

IF (INT(xA) о xA) AND (INT(xB) <> xB) THEN LET AC » AC ♦ 2 л Andi END IF

LET xA= INT(xA)

LET xB = INT(xB)

IF (xA = 0) OR (xB = 0) THEN EXIT FOR NEXT Andi LET And32 = AC END IF

END FUNCTION

REM /.........................-................/

FUNCTION Xor32(xAjcB)

DECLARE NUMERIC Xori. XC

LET XC = 0 FOR Xon=0 TO 31 LET xA = xA/2 LET xB = xB /2

IF <({NT(xA) = xA) AND (WT(xB)o xB)) OR (MT(xA) о xA) AND (INT(xB) = xB) THEN LET XC * XC + 2 A Xori ENO IF

LET xA= INT(xA)

LET xB = INT(xB)

IF (xA = 0)OR (xB = 0) THEN EXIT FOR NEXT Xori LET Xori ■ Xori ♦ 1 IF (xA =0) AND (xB = 0) THEN elselF xA = 0 THEN FOR Xon*Xori TO 31 LET xB =xB /2 IF INT(xB)OxB TFCN LET XC * XC + 2 A Xori

END IF

LET хВ = INT(xB)

IF хВ = О THEN EXIT FOR NEXTXori ELSE

FOR Xori=Xori TO 31 LET xA = xA/2 IF INT (xA) о xA THEN LET XC * XC + 2 A Xori END IF

LET xA= f4T{xA)

IF xA = 0 THEN EXIT FOR NEXTXori ENOIF

LET Xor32 = XC E№) FUNCTION

REM /........................................I

FUNCTION SL32U(xAjcL)

REM 2006-05-31 DECLARE NUfcERIC slAH.slAL

IF (xA * 0) OR {xL - 0) THEN LET SL32U = xA ELSEIF xL>= 16 THEN

LET siAL = xA • INT(xA /65536) * 65536 LET siAL = siAL • 2 A (xL ■ 16)

LET siAL s siAL • INT(siAL / 65536) * 65536 LET SL32U = siAL * 65536 ELSE

LET siAL = xA - INT(xA / 65536) * 65536 LET siAH = INT(xA / 65536)

LET siAL = siAL • 2 A xL LET slAH - slAH * 2 A xL LET slAH = slAH - INT(SlAH / 65536) * 65536 LET SL32U = siAL + slAH * 65536 PNn IF

END FUNCTION

REM /...............................*.........../

FUNCTION SR32U<xA.xL)

REM 2006-06-03 IF xL = 0 THEN LET SR32U = xA ELSEIF xA = 0 THEN LET SR32U = 0 ELSE

LET SR32U = INT(xA / 2 A xL)

END IF

END FUNCTION

REM /.........................................“V

FUNCTION Mul32U(xA.xB)

REM Г**** A.B : irtstgred long (32-bil) *****/ REM 2006-06-02

DECLARE NUMERIC MAH. MAL. MBH. MBL

LET MAH = INT(xA/65536)

LET MBH = INT(xS 165536)

IF (xA = 0) OR (xS = 0) THEN

LET Mul32U = 0

ELSEIF (МАИ = О) ANO (М8Н = 0) THEN LET Mul32LI = хА ’ кВ ELSE

LET MAL = хА - INT(xA / 65536) ’ 65536 LET MBL = xB • INT(xB / 65536} ’ 65536

LET MBH = MAH * MBL + MAL ‘ MEH ♦ INT((MAL * MBL)/65536)

LET MBH = MBH • INT(MBH / 65536) * 65536 LET MAL s MAL * MBL LET MBL = MAL • INT(MAL / 65536) * 65536 LET MU32U = MBL * 65536 ’ MBH ENO F

END FUNCTION

B.6 Примеры

В тэбгмце В.2 приведены примеры поспеаоватегъностей случайных чисел, попучаиых с испольэоеам*-ем программ, приведенных е приложении В с устамовлем-ыми значениями параметров (для проверки). Первые 5 псевдослучайных чисел и 5 псевдослучайных чкел с промежуткам в 1000 приведены для сравнения

W

w


Таблице В.2 — Примеры случайных чисел

Метод

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

Грехлараметричес-

Пятилараметри-

К омби нироеанн мй

Метод Мероенна

Физическое

генерации

метод

ми метод GFSR

чео>ий метод GFSR

метод Таусеорге

Теис тара

случайное число

Обращение « фушцт.

1СОпд32_31

1СОП031

flfsr_31

д»аг5_31

taus88_31

genrand.31

гп<ЯаЫ»31

Параметры

М-2”

m« 2»1 - 1.

Р ■ 1 279.

р« 521.

Ухаавмные в

Указанные в

Файл

настоящем

настоящем

pmd01. bar

стандарте

стандарте

А е 1 664 52».

• • 2100 005341.

<?• 418.

9т • «6.

С ■ 1

С» 0

»• 32

0г- 197. <fj* 447.

W 32

Обращемте к инициализации

1лй_1сопд32

ши_1сопд31

(nil_gf$r5

imi_iaus88

inii_genrand

иа_л1<11аыв

Начальное число дли инициализации

19 660 809

19 660 809

19 660 809

19 660 809

19 660 809

19 660 809

19 660 609

Результаты

номер случайного

Случайное число

числа

1

1 276 136 251

1 990 801 112

716 530 710

716 530 710

116464 117

652 430 828

57 316 494

2

665 096 703

549 4 24 302

1 004 066 893

1 004 066 893

1 350 114 716

769 118 065

905 630 297

3

1 405 063 418

2 128 986 934

1 27 1 815 862

1 271 815 862

14 524 262

902 64 3 984

1 460 801 524

4

1 021 835 442

637 203 998

955 533 625

955 533 625

565 035 872

1 576 219 271

751 624 663

5

1 313 6 85 521

965 379 446

626 736 785

626 736 785

1 079 577 460

859 869 705

1 289 292 436

1 000

1 292 340 048

294 6 52 208

1 58 8 358 1 91

1 935 299 389

1 404 867 807

1 194 038 620

2 001 042 935

2 000

517 257 756

407 927 492

2 02 7 766 761

43 896 710

2 022 781 177

563 296 554

1 638 049 143

3 000

1 420 573 800

216 557 927

1 495 802 935

1 516 572 896

2 098 228 799

1 515 829 663

4 1 578 219

4 000

1 195 033 140

919 6 39 774

1 360 928 075

1 923 029 091

1 089 352 213

1 803 857 212

67 938 653

5 000

971 701 120

639 093 944

1 950 421 053

2 1 29 964 021

262 361 229

1 203 434 155

1 851 047 367


ГОСТ Р ИСО 28640—2012


Приложение ДА (справочное)

Сведения о соответствии ссылочных международных стандартов ссылочным национальным стандартам Российской Федерации

Таблица ДА.1

Обозначение ссылочною международного стандарта

Степень

Обо»г<енк« ш маиисиомиие соответствующего иаияокалъиого стандартов

ИСО/МЭК 2382-1:1993

«

ИСО 3534-1:2006

е

ИСО 3534-2:2006

е

* Соответствующий национальный стандарт отсутствует. До его утверждения рекомендуется использовать перевод на русский язьж данного международного стандарта. Перевод датаюто международного стандарта находится в Федеральном тформаииотом фонде технических регламентов и стандартов.

Библиография

(11 ISO 80000-2 Quantities and units — Part 2: Mathematical signs and symbols to be used in the паЬха) sciences and technology11

[2] 1ЭОЛЕС 9899 Programming languages — C

(3 FERRENBERG A.M.. LANDAU O.P. and WONG YJ. Monte Culo Simulations: Hidden Errors from'Goorf Random Number Generators. Physical Revew Letters. 69(23). 1992. pp. 3362—3384 (4] GENTLE J.E. Random Number Genera bon and Monte Carlo Methods. Springer-Vertag, 2003 (3 HERINGA J.R^ BLdTE H.W. J. ato COMPAGNER A New Primbve Trinornals of Mersenne-Exponent Degrees lor Random-Number Generation. International Journal of Modem Physics C. 3(3). 1992. pp. S61—564

[6]    ISHtDA M.. SATO T. SUZUKI K.. SHIMADA S. and KAWASE T. Random Number Generator Using a Diode Noise. The Institute of Statistical Mathematics Research Memorandum. Number 968. 2005

(7]    jOhMK M.D. Erzeugung Von Betavesteilten und Gammavestedten Zufelszahlen. Methca. 8(1), 1964. pp. 5—15

(3    KNUTH D.E. Seminumencal Algorithms (The Art of Computer Programming. Volume 2). 3rd. ed.. Adtfrson Wesley.

1998

[9] KURTTA Y. and MATSUMOTO M. Primitive t-norr*ate (t = 3. 5) over GF (2) Whose Degree is a Mersenne Exponent и 44497. Matoematics of Computation. 56(194). 1991. pp. 817—821 [10J L’ECUYER P Maximally Equidstnbuted Combined Tausworthe Generators. Mathematics of Compulsion. 65(213). 1996. pp. 203—213

[11]    L’ECUYER P Tables of Maximaty-Equidistrbuted Combined LFSR Generators. Mathematics of Computation, 68(225). 1996. pp. 261—269

[12]    LEWIS T.G. and PAYNE W.H. Generalized Feedback Shift Rerpster Pseudorandom Number Generators. Journal of the Association for Computing Machinery. 20(3). 1973. pp. 456—468

[13 MASSEY J.L. Shrtt-Regster Synthesis and BCH Decoding. IEEE Trans, on Information Theory. IT-15 (1). 1969. pp. 122—127

[14]    MATSUMOTO M. and NtSHIMURA T. Mersenne Twister. A 623-Oimensionaily Equidistributod Unifcxm Pseudo-Random Number Generator. ACM. Trans. Model. Comput. Simul.. 8{1X 1998. pp. 3—30

[15]    VON NEUMANN J. Various Technques Used in Connection with Random Digits. Monte Cario Method. Appfeed Mathematics Series. No.12. U.S. National Bureau of Standards. Washington D.C.. 1951. pp. 36—38

[13    NIKI N. Machine Generation of Randum Numbers. The Institute of Statistical Mathematics Research Memorandum.

Number 969. 2005

[17]    NIKI N. Physical Random Number Generator for Personal Computers. The Institute of Statistical Mathematics Research Memorandum. Number 970. 2005

[18]    RUEPPEL RA. Analysis and Design of Stream Ciphers. Springer-Verlag. 1986

[13 TAUSWORTHE R.C. Random Numbers Generated by Linear Recurrence Modulo Two. Mathematics of Computation. 19. 1965. pp. 201—209

[20]    TEZUKA S. and L’ECUYER P Efficient and Portable Combined Tausworthe Random Number Generators. ACM. Trane. Model Comput. Sanut.. 1. 1001. pp. 00 112

[21]    VATTULAINEN L, ALA-NISSILA T. and KANKAALA K. Physical Tests for Random Numbers in Simulations. Physical Review Letters. 7319). 1994. pp. 2513—2516

[22]    VATTULAINEN I.. ALA-NISSILA T. and KANKAALA K. Physic^ Models as Tests of Randomness. Physical Review. E52. 1995. pp. 3205—3214

[23 Random Number Generator. The Institute of Statistical Mathematics. http://random.ism.ac.]p‘random_afindex.php

Международному стандарту ISO 800002009 соответствует РОСТР 54521—2011 «Стзтисттеские мето-№. Математические симеогш и знаки для применения а стандартах».

УДК 658.562.012.7:65.012.122:006.352    ОКС 03.120.30    Т59

Кгочееые слова: псевдослучайное число, физическое случайное число, начальное число, генератор случайных чисел, двоичные числа

Редактор С. Д. Золотова Технически редактор В. Н. Прусакова Корректор С. В. Смирнова Компьютерная верстка 7! Ф. Кузнецовой

Сдано в набор 23 06-2014 Подписано • печать 22.07.2014. Формат 60 x 841/t Бумага офсетная Гарт тура Армал Печать офсетная. Уся. печ. л. 4,65. Уч.-яад. л. 4.10 Тираж 40 экэ Зак. 1056

•ГУЛ «СТАНДАРТИ МФОРМ •. 123665 Мосяаа. Гранатный пер . 4 iu    info^postinfo.nt

Набрано я отпечатано в Калужской типография стандартов. 24602т Калуга, уя Московская. 256