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 г. № 1274-ст

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

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

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

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

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

© Стандартинформ, 2014

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

Содержание

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

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

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

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

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

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

Приложение А (справочное) Таблица физических случайных чисел

Приложение В (справочное) Алгоритмы генерации псевдослучайных чисел

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

ГОСТ Р ИСО 28640—2012

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

Статистические методы

ГЕНЕРАЦИЯ СЛУЧАЙНЫХ ЧИСЕЛ

Statistical methods. Random variate generation

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

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

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

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

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

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

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

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

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

ИСО/МЭК 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: Applied statistics)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 1 — Правила побитовой логической операции Ф

1Ф1=0,

ОФ 1 = 1,

1Ф0 = 1,

ОФ 0 = 0.

Пример побитовой логической операции Ф: 1010 Ф 1100 = 0110;

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

Пример 2 — Правила побитовой логической операции т А к

1 А1 = 1,

0 Л1 = 0,

1 Л 0 = 0, 0 А 0 = 0.

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

т := к — замена значения т на значение к]

т » к — сдвиг вправо двоичного целого числа т на к битов;

т « к — сдвиг влево двоичного целого числа т на к битов.

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

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

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

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

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

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

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

= с₽-1 + Ср.2 + - + С1 *гн1 + хп (mod 2) (л = 1,2, 3, ...).

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

  • c) Полином

t + (₽•’ + ... + С,( + 1

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

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

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

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

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

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

Xrt+P =Xrt+Ql Ф Хп^2 ф Хп+9з Ф Хп(п = 1, 2, 3...).

Параметры (р, q1( q2, Q3, w) и X1t.... Хр первоначально задают как начальные числа. Примеры параметров р, qv q2, <7з с наибольшим периодом (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

П p и м еч а н и e —Аз являются показателями степени ненулевых членов характеристического полинома.

GFSR — Generalized Feedback Shift Register.

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

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

Хгнр = (Xmg + Хп) (mod 2), (п = 0,1,2,...),

где х0, x1t х2,... — соответствующая М-последовательность.

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

Хпxnt ■■■ *ии» (л — 0, 1,2, ...),

где t — натуральное число взаимно простое с периодом (2^-1 ^-последовательности;

w — длина слова, не превышающая р бит.

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

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

Пример — Если в качестве исходного выбран многочлен t4*1 +7, установлены параметры р=4 и q=1 и в приведенной выше рекуррентной формуле заданы начальные числа (х(123) = (1,1,1,1), то М-последовательность, полученная в соответствии с рекуррентной формулой, будет иметь вид: 1,1,1,1, 0,0,0,1, 0,0,1,1, 0,1,0,1, 1,1,1,0, ..., с периодом (2* - 1) » 15. В случае t » 4 (4 является взаимно простым числом по отношению к 15) и w -4 простая последовательность Таусворта (Хп) с параметрами (4, 1, 4) имеет вид

X0-x0XfX2x3 = 1111 (= 15),

X1=x4xsx6x7 = 0001(= 1),

Х2 = Xg Xj XfQ x^ = 0011 (a 3),

X3 = x12 X14 xo ~ 0101 (= 5),

X4 « x1 x2 x3 x4 « 1110 (• 14),

Xs = xs x6 x7x8 = 0010 (= 2).

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

Если имеется несколько, например, J простых последовательностей Таусворта {*«J), У = 1,2.....J

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

Хп = Х<1,Л ®Х(2,П® ... ®XJ)n(n = 0, 1,2, ...).

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

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

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

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

Хлч, = Ф (Х'„ |Х1„,)М А, (п = 1, 2, 3,...),

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

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

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

(X 'п1о+1)м—двоичное целое число, полученное конкатенацией чисел Х„ и Х1п+1, когда первые (w—г) битое взяты изХп, а последние г битов из (Хо+1) в том же порядке;

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

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

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

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

у.= хп,

у := уф (у» и),

У := У Ф [(у « s) а Ь], у:=уф[(у« /)лс], у:=уф(у» /), где Ь, с — постоянные маски битов для улучшения рандомизации первых (w-г) битов.

Параметрами этого алгоритма являются (р, q, г, w, а, и, s, t, I, b, с). Начальными числами являются X2....,Xq.t и первые (w — г) битов числа X].

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

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

  • 6.1 Введение

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

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

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

р(у) — функция дискретного распределения.

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

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

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


1, если 0£у 51

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 — Случайные числа, соответствующие стандартному равномерному распределению, называют стандартными равномерными случайными числами и обозначают Ub U2.....Эти числа считают

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

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

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

11/ Ь, если а£у<а + Ь

0, если у g [а, а + О] ‘

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

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

Y = bU + а.

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

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

    f(y) =


    B(c,d)


    , если 0 < у < 1


О, если у е [0,1]

1

гдеВ(с,<У) = Jxc_,(1-x)tf_‘dx —бета-функция с параметрами с и d (с > 0. d > 0).

0

  • 6.3.2 Метод Йонка

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

Если Y = U*c + U2d< 1. то Y = U*c IY ; в противном случае генерируют два новых стандартных равномерных случайных числа до тех лор, пока неравенство не будет выполнено.

  • 6.3.3 Метод Ченга

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

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

a) q =


2cd-(c+d) c+d-2


, в противном случае


Ь) Вычисляют

V = 1 —IV = cexp(V).

с) Если тогда

(c+d)ln

(c+q)V-ln4 >1п(Ц2и2),


И/

Y = . ... (выход). d+W

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

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

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

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

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

b- а-у

f(y)~


---, если а-b £а+Ь ь2

0, если у ё [а-Ь,а+Ь]

где b > 0.

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

Если стандартные равномерные случайные числа Uy и U2 независимо генерированы методом, установленным в 6.2.1, то случайное число У, подчиняющееся треугольному распределению, определяют по формуле У = а + b (Uy + U2 - 1 )-

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

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

    f(y) =


    0,


    ехр {-(у-а) / Ь), у^а


у <а

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

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

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

У = -Ыл(С) + а.

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

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

f(z) = -7J=exp|--L(z-n)2|, -«<z<«,

V2xc [ 2и2 J

где ц и о — среднее и стандартное отклонение нормального распределения соответственно.

Примечание — Обычно нормальную случайную величину обозначают Z.

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

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

Zy = Ц + О 005

Z2 = у + a J-2\n(l-Uy) sin (2nU2).

Примечание 1 — Поскольку Uy — дискретная величина, то Zy, Z2 не подчиняются нормальному распределению в строгом смысле. Например, используя эту процедуру, верхней границей абсолютных значений псевдослучайных стандартных нормальных величин является м = 7-21п(т"1) = ^21пт ■ Таким образом, если т - 2зг то я 6.6604. а если т = (231 - 1), то М » 6.5555. Однако, так как вероятность того, что абсолютные значения случайных величин истинного стандартного нормального распределения, превышающих М, приблизительно равна Ю~10 . это редко создает трудности на практике.

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

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

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

    f(y) =


—— {(у - а)/Ь}с 1 ехр{-(у - а)!Ь}, если у > а оГ(с)

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

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

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

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

  • 6.7.2.2 Алгоритм для с = к (к — целое число)

Используя независимые равномерные случайные числа UVU2.....Uk, применяют формулу

у = а-Ып{(1 - U1X1 - U2)... (1 - Uk)}.

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

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

Используя стандартное нормальное случайное число Zq и равномерные случайные числа U1t U2, Uk, применяют формулу

Y= а + b[z02/2-ln{(1-U1)(1-U2)...(1-UJ}|.

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

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

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

  • a) Задают г = с - 1/3, s = ,t = г-г ln(r), р = 1/(3 Vs ) и q = - 3 Vr.

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

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

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

  • e) Если (У- r)2!Y- V<U. выполняют У := a +bY(конец).

  • f) Вычисляют W = У-г1п(У) -t- V.

  • g) Если W< U, то выполняют У := a +bY (конец).

  • h) Если W> -1п(1,0 -1/), то переходят к Ь).

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

  • б.7.2.5 Точный метод генерации Ченга для с * 1/2

  • a) Задают q - с- In 4 и г = с + V^c-1 .

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

  • c) Вычисляют V = dn^1 j. W= с exptt/j). Z = t/2 U2, R = q + rV - W.

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

  • e) Если R > InZ, то вычисляют У = a + bW (выход).

  • f) Генерируют стандартные равномерные случайные числа Uy и U2 и вычисляют

р = 1/V2C-1 , q = с - 1п4, г = с + ^2с-1 -

Если q + prln


,1-J-C(1-J,>245^)-(1+In45)-

то У = а + Ьс J (выход).

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

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

    F(y) =


    если у>а


, если у<а

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

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

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

Y = а-Ь{1п(1

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

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

    -=------exp

    /27{(у-а)/Ь)


    “) еслиУ-а


0.


если у<а

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

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

Используя стандартные нормальные случайные числа Z, применяют формулу

Y = а + exp(b-Z)

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

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

  • 6.10.1 Функция вероятности где а и b— параметры положения и масштаба соответственно.

    Р(У) =


    _____________1_____________

    1 + ехр{-(у-а)/Ь}'


    —фф


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

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

у=а+ь|пШ-

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

Случайные числа Yb Y2,...» Yn, соответствующие л-мерному нормальному распределению со средними Ц2- -- -Цл- дисперсиями и ковариациями о*(1 получают, используя взаимно независимые

стандартные нормальные случайные числа Z1.....Zn

Y' = ^ + a„ Z1f

Хг “ М2 + а21^1 * а22^2-

Уп = Мп + ao1^i + ал2^2 +- + апгЛ.

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

Примечание — Оу(1 < /. j<n) ковариации, о, — дисперсии УР

  • a) Для/=1 au=Jv^, ал = <snfau (2</< л).

  • b) Для j = 2, .... п






(/+ 15 i < п)

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

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

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

Р(У) = (ура-РГ". У =0,1.....п,

где 0 < р < 1.

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

  • 6.12.2.1 Общие положения

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

  • 6.12.2.2 Прямой метод

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

  • 6.12.2.3 Метод обратной функции

Вычисляют функцию распределения

F(y) = ра-рГ". у=ол.... п.

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

  • 6.12.2.4 Метод положения

Вычисляют (л + 1) параметров Vq, V),.... vn и (л + 1) параметров а0, a1t..., ал.

  • a) vy = (л + 1)р(/), / = 0, 1,

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

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

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

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

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

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

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

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

  • e) Вычисляют к = L VJ и и = V-к, где LVj — целая часть числа V.

  • f) Если и < vk, то Y = к; в противном случае У = ah

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

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

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

Р(У)= угехр(-ц), у= 0,1,2.....

где р > 0.

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

Генерируют стандартные равномерные случайные числа Ub U2,.... В качестве /используют макси* мальное значение п, удовлетворяющее следующему неравенству

_1п<(1 - ^0(1 -М2)... (1 -

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

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

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

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

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

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

2*'1+1 <. N-M + 1 <2к.

Примечание1 — Величина к — наименьшее натуральное число, удовлетворяющее неравенству ks tog2(W-М + 1).

Пример 1 — Если (N - М + 1) = 100, то к = 7, поскольку^ + 1) = 65 £ 100 £27 = 128.

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

Примечание2 — k-битовое двоичное число Z^Z2Z2Z4.. .Zk соответствует десятичному числу 2*-1Z, + 2*"2Z2 + 2*"3Z3 + 2*“*Z4 +... + Zk.

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

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

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

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

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

  • d) Генерируют последовательность десятичных случайных чисел из /гцифр. используя процедуру 5.2.

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

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

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

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

В отличие от псевдослучайных чисел у физических случайных чисел отсутствуют функциональная связь и периодичность. 8 таблице А.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

88

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

28

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

06

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

98

41

77

78

24

26

98

03

14

25

73

84

48

28

13

55

81

09

70

17

78

18

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

98

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

68

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

60

31

55

42

68

53

27

82

67

68

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

80

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. использован электрический шум диода. В диоде шумовой сигнал достаточно велик вследствие эффекта лавинного нарастания заряда. Поэтому диод часто используют как источник шума. Был использован лавинно-пролетный диод NC24014 У этого элемента есть источник шума и встроенный усилитель, ширина полосы частот которого составляет 1 ГГц. а амплитуда — 160 мВ.

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

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

  • b) наблюдение последовательности импульсов с определением количества импульсов в единицу времени;

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

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

Например, для аналоговоцифрового преобразования может быть использован конвертер DAS-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. Метод Мерсенна Твистера обычно инициируют функцией init_genrand (s), где s = 19660809. Если необходимы оригинальные последовательности случайных чисел, они могут быть восстановлены с помощью единственного или повторного использования метода Мерсенна Твистера.

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

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

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

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

В.1 Текст программы трехпараметрического метода GFSR

Ниже приведен текст программы на языке Си. которая в соответствии с ИСО/МЭК 9899 является примером метода GFSR с параметрами (р, q, w) - (1279. 418. 32) и периодом (21279 - 1). При обращении к функции gfsr () происходит генерация целого числа из интервала от 0 до (232 — 1) включительно. При обращении к функции gfsr_31 () происходит генерация целого числа из интервала от 0 до (231 - 1) включительно. Для обращения к функциям gfsr () и gfsr_31 () необходима единственная инициализация init_gfsr (s). Функция init_gfsr (s) выполняет инициализацию при условии, что в качестве начального числа используется 32-битовое целое число без знака (целое число из интервала от 0 до (232 - 1)]. Полученная последовательность обеспечивает 39 независимых серий псевдослучайных чисел, каждая из которых обладает незначительной автокорреляцией, имеет 39-мерное распределение (однородно распределена в 39-мерном гиперкубе) с 32-битовой точностью, и ее функция автокорреляции такова, что значения близкие к нулю появляются через 21?74 чисел.

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

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

Г’****........*...................*..............

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

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

«define Р 1279 «define Q 418 «define W 32 /* значения W должны быть степенью 2 */

sialic unsigned long slate [P] . static int state_i ;

void init_gfsr (unsigned long s)

{ int i. j, k; static unsigned long x [P];

s&= OxffffffffUL;

for (i=0 ; i<P ; i++) {

x [i] = s»31 ;

s = 1664525UL ’ s + 1UL ;

s &= OxffffffffUL;

}

for (k=0. i=0; i<P; i++) {

state [i] = OUL ;

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

state [i] «= 1; state pl |= x [k]; x(k]A=x((k+Q)%P]; k++;

if (k==P) k = 0;

} } state_i = 0;

}

unsigned long gfsr (void)

{ int i;

unsigned long *р0. *р1 ;

if (state_i >= Р) {

state_i = 0;

рО = state;

р1 = state ♦ Q ;

for (i=O ; i<(P-Q); i++)

*pO+* A= *p1++ ;

p1 = state;

for (; i<P; i++)

*pO++ A= 'p1+* ;

}

return state [state_i++];

}

Г (W-IJ-битовое целое 7

long gfsr_31 (void)

<

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

}

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

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

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

REM ...................

OPTION BASE 0

REM

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

DECLARE NUMERIC P LET P=1279

DECLARE NUMERIC Q

LET Q=418

DECLARE NUMERIC W

LET W=32


.........I

!#define P 1279

!#define Q 418

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

DIM state(P) DECLARE NUMERIC state i


!static unsigned long statefP]; ■static INT slate i;


REM

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

FUNCTION init_gfsr(s) !

DECLARE NUMERIC i.j.k DIM x(P)

LET s = And32(s . MskFJ)

FORi = OTOP-1

LET x(i) = SR32U(s , 31)

LET s = Mul32U(1664525 . s) ♦ 1

LET s = And32(s. MskFJ)

NEXT I

LET k=0

FORi = OTOP-1

LET state(i) = 0

FORj=0 TOW-1

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

LET state(i) = Or32(state(i), x(k))

LET x(k) = Xor32(x(k). x (REMAINDERS ♦ Q . P))) LETk = k+ 1

IFk = PTHEN LETk = 0


! !

i

i

I

i

i

i

I


void init_gfsr(unsigned long sX int i. j. k; static unsigned long x(P); s &= OxffffffffUL; for (i=0; i<P; i++) { xffl = s»31;

s = 1664525UL * s + 1UL; s&= OxffffffffUL;

}


for (k=0. i=0; i<P; i++) { statefi] = OUL;

for (j=0; j<W; j++) { statefi] «= 1; statefi] |=x[k]; x[k]A=xf(k+Q)%P]; k++;

if (k==P) k = 0;


NEXTj NEXTI

LET state_i = 0

END FUNCTION

REM

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


I }

I }

! state_i = 0

!}

/


FUNCTION gfsr

DECLARE NUMERIC I

DECLARE NUMERIC pO, p1

IF state.i >= P THEN LET state J = 0 LET pO = 0 LET p1 = Q1 FORi=OTO P-Q-1

LET statefpO) = Xor32(state(p0). state(pl)) LET pO = pO + 1

LET p1 = P1 + 1

NEXT!

LET p1 = 0

FOR i=i TO P-1

LET state(pO) = Xor32(state(p0), state(pl)) LET pO = pO + 1

LET p1 =P1 + 1

NEXT!

END IF

LET gfsr = state(statej)

LET state_i = state J + 1

END FUNCTION

REM


! unsigned long gfsr(void){

I int i;

I unsigned long *p0. ap1;

I if (state_i >= P) {

I state_i = 0;

I pO = state:

I p1 = state+ Q1;

! for (i=0; i<(P-Q); i++)


I *pO++ A= *p1++;

! p1 - state;

I for (; i<P; i++)


I ’p0++ A= *p1++;

I }

I return state(state_i++];

! )


REM Г (W-1)-6nToeoe целое 7 FUNCTION gfsr_31

I long gfsr_31(voidX


return (longXgfsr()»1);


LET gfsr_31 = SR32U(gfsr, 1) END FUNCTION

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

Параметры и период данной программы составляют (521. 86, 197, 447, 32) и (2521 - 1). При обращении соответственно к функции gfsr5() происходит генерация целого числа из интервала от 0 до (232 -1) включительно. При обращении к функции gfsr5_31() происходит генерация целого числа из интервала от 0 до (231 - 1) включительно. Функция init_gfsr5 (s) выполняет инициализацию при условии, что начальное число является 32-битовым целым числом без знака [целое число из интервала от 0до(2зг-1)]. До обращения к функции gfsr5 () и gfsr5_31 () необходимо выполнить первоначальную инициацию init_gfsr5 (s). Полученная последовательность имеет 16-мерное распределение (равномерное распределение в 16-мерном гиперкубе) с 32-битовой точностью, а ее функция автокорреляции такова, что период появления близкого к нулю значения составляет 2516.

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

Если необходима другая последовательность с другим периодом, то значения р, Qi, q2 и Оз необходимо

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

I.........................................——.................. 7

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

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

«define Р 521


Г Q1 < Q2 < Q3 7 «define Q1 86 «define Q2 197 «define Q3 447

«define W 32 Г W должно быть степенью 2 7

Static unsigned long state [P] ;\ Static int statej;

void init_gfsr5 (unsigned long s)

{

int i, j, к ;

static unsigned long x [P];

s &= OxfffflTffUL;

for (i=0 ; i<P ; i++) {

x (i] = s»31 ;

s = 1664525UL * s + 1UL;

s &= OxffffffffUL;

}

for (k=0, i=0 ; i<P ; i++) {

state (i] = OUL ;

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

state [i]«» 1 ;

state [i] |= x [kJ;

x [k] A=x [ (k+Q1) %P] Ax ((k+Q2) %P] Ax ((k+Q3) %P];

k*+;

if (k==P) к = 0;

}

state_i = 0;

}

unsigned long gfsrS (void)

{

inti;

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

if (state_i >= P) {

state_i = 0;

pO = state;

p1 = state + Q1 ;

p2 = state ♦ Q2;

p3 = state ♦ Q3 ;

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

*p0++ A= *p1++ A *p2++ A *p3++;

p3 = state;

for (; K(P-Q2); i++)

*p0++ A= "p1++ A "p2++ A*p3++;

p2 = state;

for (; i<(P-Q1); i++)

*pO+-+ A= ’p1++ A *p2++ A*p3++;

p1 = state;

for (; i<P ; i++)

•pfrt-t- *= *р1*ч- A*p2+* A*p3*4‘,

}

return state [state_i++];

}

Г (W-IJ-битовое целое 7

long gfsr5_31 (void)

{

return (long) (gfsr5() »1);

}

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

REM

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

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

/*’•’**’..................................*...........................*.......7

OPTION BASE 0

REM

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

DECLARE NUMERIC P LET P = 521

REM Г Q1 < Q2 < Q3 7

DECLARE NUMERIC Q1 LET Q1 = 86

DECLARE NUMERIC Q2

LETQ2 = 197

DECLARE NUMERIC Q3 LET Q3 = 447

DFCI ARF NIJMFRIC W

LET W = 32

’«define P 512

’«define Q1 86

’«define Q2 197

•«define Q3 447

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

’«define W 32


DIM state(P)

DECLARE NUMERIC statej

REM

Г”***.........................................

FUNCTION init_gfsr5(s)

DECLARE NUMERIC i.j.k

DIM x(P)

LET s = And32(s . MskFJ) FOR i=OTO P-1

LET x(t) = SR32U(s . 31) LET s - Mul32U(1664525 , s) * 1 LET s = And32(s . MskF f)

NEXT I

LET k=0

FOR i=0 TO P-1

LET stale(i) = 0

FORj=0 TOW-1

LET statefi) = SL32U(state(i), 1) LET state(i) - Or32(state(i). x(k)) LET x(k) = Xor32(Xor32(Xor32(x(k) x(REMAINDER(k + Q1 , P))) x(REMAINDER(k + Q2 . P))) x(REMAINDER(k + Q3, P)))

LET к = к + 1

IF к = P THEN LET К = 0 NEXTj

NEXT I

LET statej = 0

END FUNCTION


’static unsigned long $tate[P]; ’static int statej;


•7

’void init_gfsr5(unsigned long s) {

’ int i, j. k;

I static unsigned long x(P);

’ s &= OxffffffffUL;

’ for (i=0; i<P; i++) {

! x[i] = s»31;

! $ - 1664525UL ’ S 1UL.

’ s 8s OxffffffffUL;

}

’ for (k=0.i=0; i<P; i++) {

’ state[i] = OUL;

i for (j=0; j<W; j+*) {

’ statefi] «= 1;

’ statejij |=x[k];

’ x(k]A=x[(k+Q1)%P]Ax((k+Q2)%PlA

x[(k+Q3)%PJ;


’ k++;

’ if(k==P)k = O;

}

}

’ statej = 0;

0


REM

Г...........•...................*...........

FUNCTION gfsr5 DECLARE NUMERIC I

DECLARE NUMERIC pO. p1, p2. p3

IF statej >= P THEN LET statej - 0


"7

’unsigned long gfsr5(void) {

< int i;

’ unsigned long ’pO. *p1. *p2. *p3;

’ if (statej >= P) {

’ statej = 0;


LET рО = 0

LET p1 =Q1

LET р2 = Q2

LET рЗ = Q3

FOR i=O ТО P-Q3-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 рЗ = 0

FOR i=i TO P-Q2-1

I FT Rtate(pn) = Xrr3?(Xnr3?(Xor3?(siate(pO) . state(p1)), state(p2)). state(p3))

LET pO = pO + 1

LET p1 = p1 1

LET p2 = p2 + 1

LET рЗ = p3 + 1

NEXTi

LET p2 = 0

FORi=i TO P-Q1-1

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

LET pO = pO + 1

LET p1 = p1 + 1

LET p2 = p2 + 1

LET рЗ = p3 + 1

NEXTi

LET p1 = 0

FOR i=i TO P-1

LET state(pO) = Xor32(Xor32(Xor32(state(p0) slate(pl)). state(p2)), state(p3))

LET pO = pO + 1

LET p1 = p1 + 1

LET p2 = p2 + 1

LET рЗ = p3 + 1

NEXTi

END IF

LET gfsr5 = state(state_i)

LET state_i = state_i ♦ 1

END FUNCTION

REM

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

REM Г (W-1)-6wTO8oe целое •/

FUNCTION gfsr5_31

LET gfsr5_31 = SR32U(gfsr5 . 1)

END FUNCTION

! pO = state;

! p1 = slate

’ p2 = state

! p3 = state

’ FOR (i=0; K(P-Q3); i++)


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

’ p3 - stale;

’ for (; i<(P-Q2); i++)

J 'p0++A= *p1++A *p2++A’p3++,

’ p2 = state;

! for (; i<(P-Q1); i++)


I *p0+* A= "p1++ A wp2++ A’p3++;

’ pi = state;

! for(; i<P; i++)


! "p0++A=’p1++Л *p2*+A“p3*+;

! }

! return state[state_i++];

0

"•/

Hong gfsr5_31(void) {

’ return (Iong)(gfsr5()»1);

0


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

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

Инициализация init_taus88 (s) происходит при условии, что начальное число s является 32-битовым целым числом без знака (целое число из интервала от 0 до (232 - 1) включительно]. Для получения другой последовательности псевдослучайных чисел необходимо изменить начальное число s. Перед обращением к taus88_31 () необходимо один раз выполнить инициализацию init_taus88 (s). Инициализация может быть выполнена без использования функции ir>rt_taus88 (s) с помощью выбора подходящих значений s1t s2 и $з- Однако для инициализации должны быть выполнены следующие три условия:

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

  • - хотя бы один разряд из высших 29 разрядов S2 равен единице;

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

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

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

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

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

static unsigned long s1, s2. s3, b ;

void ir>il_taus88 (unsigned long s)

{

int i;

unsigned long x [3];

i=0;

while (i<3) {

if (s & OxffffiffOUL) {

x [i] = s ;

i*>;

}

s= 1664525UL ’ s + 1UL;

}

s1 = x [0]; s2 = x [1]; s3 = x [2];

}

Г 31-битовое целое 7

long taus88_31 (void)

{

b = <((s1 « 13)A si)» 19);

s1 = (((s1 & 4294967294UL) « 12) Ab) ;

b = (((s2 « 2)A s2)» 25);

s2 = (((s2 & 4294967288UL) « 4) *b);

b = (((S3 « 3)As3) »11);

S3 = (((S3 & 4294967280UL) «17) *6) ;

return (long) ((s1 A s2 A s3) »1);

}

В этой программе операторы

b = (((s1 « 13) А s1)» 19).

з1 = (((з1 & 4204967204UL) « 12) Ab)

генерируют числа в последовательности Таусворта с параметрами (31, 13, 12) в s1t а операторы

b = (((S2 « 2) А S2) » 25),

S2 = (((S2 & 4294967288UL) « 4) *Ь)

и

b = (((s3 « 3) ^ЧЗ) » 11);

s3 = (((s3 & 4294967280UL) « 17) АЬ)

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

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

Если необходимо получить независимый набор случайных чисел для каждого повторения моделирования, функцию инициализации init_taus88 (s) необходимо вызвать один раз в начале моделирования. После каждого повторения значения s^, &2 и S3 необходимо сохранять и присваивать переменным s^, S2 и S3 соответственно, как начальные значения при следующем повторении.

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

REM -----—•*——-----

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

REM

OPTION BASE 0

REM

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

FUNCTION init_taus88(s)

DECLARE NUMERIC I

DIM x(3)

FOR i = 0 TO 2

IF And32(s , MskF.O) о 0 THEN LET xfi) = s

END IF

LET s = Mul32U(1664525. s) + 1 NEXT I

LET s1 = x(0)

LETs2 = x(1)

LET s3 = x(2)

END FUNCTION REM

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


’void init_taus88(unsigned long s) {

1 kit i;

’ unsigned long x[3];

I i=0; while (i<3) {

! if (s 8 OxfffffffOUL) {

’ x(i] = s; i*+;

! }

I s = 1664525UL ’ s *1UL

! }


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


FUNCTION taus88_31

REM /•*’** 31-битовое целое wm/

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(s2 . MskF_8), 4). b)

LET b = SR32U(Xor32(SL32U(s3. 3), s3), 11 LET s3 = Xor32(SL32U(And32(s3 . MskF_0), 17). b)

LET taus88_31 = SR32U(Xor32(Xor32(s1, s2), S3), 1)

END FUNCTION


Hong taus88_int(voki)

{

! b = (((s1 « 13)As1)>> 19):

’ S1 = (<(S1 84294967294) « 12) A b);

! b = <((s2 « 2) A s2) » 25);

! s2 = (((s2 84294967288) « 4) A b);

! b = (((s3 « 3)Л s3) =» 11);

! s3 = (<(s3 84294967280) « 17) A b);

’ return (longX(s1 A s2 A s3) » 1);


B.4 Текст программы для метода Мерсенна Твистера

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

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

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

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

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

Г Параметры периода*/

«define Р 624

«define Q 397

«define MATRIXA 0x9908b0dfUL

«define UPPER.MASK Ox80000000UL «define LOWER MASK Ox7ff(ffffUL


Л постоянный вектор a 7

Г наиболее значимые (w-r) бит 7 Г последние значимые г 6ni ’/


static unsigned long mt [P];

static int mti=P+1 ;

Г инициализация mt [P] с начальным значением a 7 void init_genrand (unsigned long s)

{

mt [0] = s & OxffffffffUL ;

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

mt [mti] = (1664525UL * mt [mti-1] + 1UL);

mt [mti] &= OxffffffffUL ;

}

}

Г генерация случайного числа из интереала[0. Oxffffffff] 7 unsigned long genrand (void)

{

unsigned long у ;

static unsigned long mag01 [2] = (OxOUL, MATRIX_A};


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

Г mti==P+1 означает, что mt [Р] не инициализирован 7


Г mag01 [х] = х * MATRIX_A для х=0, i 7


if (mti >=Р) { int kk;


Г генерация Р слое одновременно 7


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


Г если init _genrand () не вызвано 7

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


for (kk=O ; kk<P-Q . kk++) {

у = (mt (kk) &UPPER.MASK) | (mt (kk+1 ] &LOWER.MASK);

mt (kk] = mt [kk+Q]A (y »1)A mag01 (y & 0x1 UL);

}

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

у = (mt [kk] &UPPER.MASK) | (mt [kk+1] &LOWER_MASK);

mt [kk] = mt [kk+ (Q-P) ]A (y » 1)A mag01 [y & 0x1UL);

}

у = (mt (P-1] &UPPER.MASK) | (mt [0] &LOWER.MASK);

mt [P-1] = mt [Q-1]A (y »1)A mag01 [y & 0x1UL);

mti = 0;

}

у = mt [mti++];

Г Темперирование 7


уА= (у »11);

у *= (у « 7) & Ox9d2c5680UL;

у *= (у « 15) & OxefcfiOOOOUL ; уА=(у»18);

return у; }

Г генерация случайного числа из интервала [0.0x7ffTffff] 7 long gervand_31 (void)

{ return (long) (genrand() »1);

)

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

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

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

OPTION BASE 0

REM

Г...........•..............................

REM Г Параметры периода 7

DECLARE NUMERIC Р

LET Р = 624

DECLARE NUMERIC Q

LET Q = 397

DECLARE NUMERIC MATRIX_A

LET MATRIX_A = BVAL(«9908b0df» . 16)


DECLARE NUMERIC UPPER-MASK

LET UPPER_MASK = BVAL(“80000000H, 16)


Wdefine P 624

!#define Q 397

!#define MATRIX_A 0x9908b0dfUL

Г постоянный вектор a 7

«define UPPER_MASK DxSOOOOOOOUL

Г наиболее значимые w-r бит 7


DECLARE NUMERIC LOWER.MASK LET LOWER_MASK = BVALCTffffffT, 16)


DIM ml(P)

DECLARE NUMERIC mti

LET mti = P + 1


REM


REM Г инициализация mt(P] с начальным значением 7 FUNCTION init_genrand(s)

LET mt(0) = And32(s . MskF_f)

FOR mti = 1 TO P -1


«define LOWER.MASK 0x7fffffffUL

Г последние значимые г бит 7 ’static unsigned long mt[P);

Г массив состояния вектора 7 ’static int mti=P+1;

Г mti==P+1 означает, что mt(P] не инициализирован 7

......../

’void init_genrand(unsigned long s) { ’ mt[O]=s&OxffffffffUL;

! for (mti=1; mti<P; mti+*) {


LET mt(mti) = Mul32U(1664525 . mt(mtM)) + 1

LET mt(mti) = And32(mt(mti). MskF f)

NEXT mti

END FUNCTION


! mt(mti) = (1664525UL * mt(mti-1] + 1UL); ! mtfmti] &= OxffffffffUL;

! }

0


REM I.....


REM Г генерация случайного числа из интервала [O.Oxffffffff] 7


FUNCTION genrand DECLARE NUMERIC у DIM mag01(2) LET mag01(0) = 0

LET mag01(1) = MATRIX.A


IF mti >= PTHEN

DECLARE NUMERIC kk

IF mti = P + 1 THEN

LET у = init_genrand(5489)

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

FOR kk=O TO P-O-1

LET у = Xor32(And32(mt(kk), UPPER_MASK), And32(mt(kk+1). LOWER_MASK))


I unsigned long genrand(void) {

! unsigned long y;

(static unsigned long mag01[2]={0x0UL. MATRIX_A};

rmag01[x] = x’MATRIX_Aforx=0.1 7

I if (mti >= P) {

Г генерация P слое одновременно 7

! int kk;

! if (mti — P+1)

Г если init_genrand() не вызван 7

• init_genrand(5489UL);


I for (kk=0kk<P-O.kk++) {

! у = (mt [kk] &UPPER_MASK) | (mt (kk*1]&LOWER_MASK);


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

NEXTkk

FOR kk=kk TO P-2

LET у = Xor32(And32(mt(kk). UPPER_MASK). And32(mt(kk+1), LOWER_MASK))

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

NEXTkk

LET у = Xor32(And32(mt(P-1) , UPPER-MASK). An<J32(ml(0) , LOWER.MASK))

LET mt(P-1) = Xor32(Xor32(mt(Q-1),

SR32U(y .1)), magO1(And32(y . 1)))

LET mti = 0

END IF

LET у = mt(mti)

LET mti = mti + 1

REM Г Темперирование 7

LET у = Xor32(y. SR32U(y ,11))

LET у = Хог32(у . And32(SL32U(y. 7). BVAL(‘9d2c5680“ , 16)))

LET у = Xor32(y. And32(SL32U(y .15). BVAL(’efc60000-. 16)))

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

LET genrand = у

END FUNCTION

REM

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

REM Г генерация случайного числа из интервала [0.0x7fffffff] 7 FUNCTION genrand_31

LET genrand 31 = SR32U(genrand . 1)

END FUNCTION-

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

!}


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

! у = (mt [kk] & UPPER_MASK) | (mt[kk+1] &LOWER_MASK);

! mt[kk] = mt[kk+(Q-P)]A(y»1)A mag01[y & 0x1 ULJ:

4

! у = (mt[P-1) & UPPER_MASK)| (ml(0]&LOWER_MASK),

! mt[P-1) = mt[Q-1]A (y » 1)A mag01 [y& 0x1 ULJ;

! mti = 0;

!}

! у = mt[mti++);

!yA=(y»11);

’ у A= (y « 7) & 0x9d2c5680UL;

!y*=(y« 15)& 0xefc60(XX)UL;

! у A= (y » 18);

! return y;

!}

/

’long genrand_31(void) {

! return (longXgenrand()»1);

0


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

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

В.5.1.1 Применение

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

В.5.1.2 Определение

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

Хп = mod (аХр., + с\ т) п = 1.2......

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

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

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

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

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

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

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

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

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

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

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

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

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

Номер строки

А

с

м

1

2

  • 3

  • 4

  • 5

  • 6

1 664 525

  • 1 566 083 941

48 828 125

  • 2 100 005 341

397 204 094

314 159 369

0

0

0

0

0

232

232

232 231-1 231_1 231 - 1

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

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

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

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

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

В.5.2 Текст программы для линейного конгруэнтного метода

В.5.2.1 Общие положения

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

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

При каждом обращении функция Icong32 () формирует случайное целое число от нуля до (2JZ — 1) включительно. Результат имеет тип «длинного целого числа без знака». При каждом обращении функция Icong32_31() формирует случайное целое число от нуля до (231 - 1) включительно. Результат имеет тип «длинного целого числа». Функция инициализации init_lcong32 (использующая длинное начальное целое без знака) выполняет инициализацию так. чтобы неотрицательное целое число типа «длинное целое без знака» было установлено как начальное число. Если второе слагаемое с = 0 и исходное начальное число Хо’ является нечетным, то Хд может быть установлено как Xq = Хо\ Однако, если задано четное исходное начальное число Xq. в случае с = 0 для получения начального числа к исходному начальному числу прибавляют единицу Xq = Xq + 1. В других случаях используют е качестве Хо начальное число mod(X^*; т).

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

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

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

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

............*.........*

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

..................

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

«define MULTIPLIER 1664525UL

«define INCREMENT 1UL

Static unsigned long state32 ; Unsigned long Icong32( void ) {

state32 = ( state32 ’ MULTIPLIER + INCREMENT ) & OxFFFFFFFFUL;

return state32;

}

long Icong32_31( void )

{

state32 = (state32 * MULTIPLIER + INCREMENT ) & OxFFFFFFFFUL;

return state32»1;

} void init_lcong32(unsigned long s) {

Г начальное число должно быть нечетным, если слагаемое INCREMENT равно 0 7

if ((INCREMENT==O) && (s%2 = 0) X

s++ ;

} state32 = s ;

}

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

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

«undef MULTIPLIER

«undef INCREMENT «undef NBIT «define NBIT 15 «define MASK ((1«NBIT)-1)

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

«define MULTIPLIER 2100005341UL

«define MULTIPLIER_LO (MULTIPLIER & MASK)

«define MULTIPLIER.™ (MULTIPLIER » NBIT)

Static unsigned long state31 ;

long Icong31 ( void )

{

unsigned long xlo, xhi;

unsigned long zO. z1, z2;

xlo = state31 & MASK;

xhi = state31 » NBIT ;

zO = xlo * MULTIPLIER.LO; Г 15bit * 15bil => 30bil 7

z1 = xlo * MULTIPLIER.HI+ xhi ’ MULTIPLIER.LO ;

Г 15bit * 16hit * 7 37hit 7

/* 16bit * 16bit => 32bit 7


Г начальное число не должно быть 0 7


z2 = xhi* MULTIPLIER-HI;

zO += (z1 & MASK)« NBIT;

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

zO = (zO & MASK2) | ((z2&1)«(2*NBIT)); z2»=1 ;

state31 = zO + z2 ;

if (state31>=0x7fffffffUL) state31 — 0x7ffffiffUL ;

Г Это число не должно превышать 2*0x7fffffffUL 7 return (long) state31 ;

}

void init_lcong31 (unsigned long $)

{

if ( s == OUL } s=19660809UL ;

s = s % 0x7fffffffUL .

state31 = s ;

J

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

REM .....................................

REM Программные коды линейного конгруэнтного метода на языке BASIC REM

REM

REM /••••—•••• ............................ ..................

REM Часть 1. Modulus - 2A32

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

OPTION BASE 0

REM

DECLARE NUMERIC MULTIPLIER

LET MULTIPLIER = 1664525 DECLARE NUMERIC INCREMENT

LET INCREMENT = 1


•«define MULTIPLIER 1664525UL

’«define INCREMENT 1UL


DECLARE NUMERIC state32

REM

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

FUNCTION Icong32

LET state32 = And32((state32 * MULTIPLIER) + INCREMENT. MskF_f)

LET Icong32 = state32

END FUNCTION

REM


■static unsigned long state32:

......./

•unsigned long Icong32u( void ) {

• state32 = ( state32 * MULTIPLIER + INCREMENT) & OxFFFFFFFFUL: ■ return state32;

0

......./


FUNCTION Icong32_31


LET Icong32_31 = SR32U(lcong32 , 1)

END FUNCTION

REM

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

FUNCTION init_lcong32(s)

REM /* начальное число должно быть нечетным. IF (INCREMENT = 0) AND (REMAINDERS . 2) = 0)

THEN

LET s = s ♦ 1

END IF

LET state32 = s

END FUNCTION


’long Icong32( void ) {

I state32 = (state32* MULTIPLIER ♦INCREMENT) & OxFFFFFFFFUL;

! return state32»1;

!}

...................."/

’void inil_lcong32(unsigned long s) { если слагаемое INCREMENT равно 0 7

! if ((INCREMENT==0) && (s%2 == 0)) {

! S++;

! }

! state32 = s;

0


REM I.........................................................

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

REM

REM

REM Часть 2. Modulus = 2A31-1 = 2147483647

REM..........................................................I

OPTION BASE 0

DECLARE NUMERIC NBIT

LET NBIT = 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 MULT1PLIER.LO LET MULTIPLIER.LO = And32 (MULTIPLIER. MASK)

DECLARE NUMERIC MULTIPLIER.HI

LET MULTIPLIER.HI = SR32U(MULTIPLIER . NBIT)

DECLARE NUMERIC state31 REM /...........................................

FUNCTION Icong31

DECLARE NUMERIC xto. xhi DECLARE NUMERIC zO, z1, z2

LET xto = And32(stale31 , MASK) LET xhi = SR32U(state31 . NBIT) LET zO = xlo * MULTIPLIER.LO

LET z1 = xlo * MULTIPLIER.HI


•«define NBIT 15

’ «define MASK ((1«NBIT)-1)

• «define MASK2 ((1«(2‘NBIT))-1)


LET z1 = z1 + xhi * MULTIPLIER.LO

LET z2 = xhi" MULTIPLIER.HI

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

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


! «define MULTIPLIER 2100005341UL

! «define MULTIPLIER.LO (MULTIPLIERS MASK)

’ «define MULTIPLIER.HI (MULTIPLIER» NBIT)

(static unsigned long state31;

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

’long Icong31( void ) {

! unsigned long xlo. xhi;

! unsigned long zO. z1. z2;

! xto = state31 & MASK, //1st val.9

’ xhi = state31 » NBIT; //1st val:600

I zO = xto ’ MULTIPLIER.LO; ri5bit*15bit => 30bit 7

! z1 = xlo * MULTIPLIER.HI + xhi * MULTIPLIER.LO;

  • • /•15bif 16bit’2=> 32bit7

! z2 = xhi ’ MULTIPLIER.HI;

Г 16bif 16bit => 32bit 7

  • • zO += (z1 & MASK)« NBIT;

//1st val:897833157

! z2 ♦= (21 » NBIT) + (zO »(2’NBIT));


LET zO = Or32(And32(zO . MASK2), SL32U(And32(z2.1), 2 ' NBIT))

LET z2 = SR32U(Z2,1)


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

Iz2»=1;


LET state31 = zO + z2

REM Л Это число не должно быть более 2*0x7ffffflfUL 7 IF state31 >= 2147483647 THEN LET state31 = state31 - 2147483647

LET Icong31 = slate31

END FUNCTION

REM

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

FUNCTION initjcong31(s)

REM ! Л начальное число не должно быть 0 7

IF s = 0 THEN LET s = 19660809

LET s = REMAINDERS , 2147483647)

LET state31 - s

END FUNCTION


! state31 = zO + z2;


I IF (state31>=0x7fffffffUL) state31-= Ox7fffffffUL;

I return (long) state31;

!}


(void initjcong31 (unsigned long s) {


! И ( s == OUL ) s=19660809UL; ! s = s % 0x7fffffffUL;

! staie31 = s;

0


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

REM /’

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

REM —....... /

OPTION BASE 0

REM /'

DECLARE NUMERIC MskFJ DECLARE NUMERIC MskT_e DECLARE NUMERIC MskF_8 DECLARE NUMERIC MskFJ)

LET MskFJ = BVAL(«ffffffff* . 16) LET MskF_e = BVAL(«ffffffie» . 16) LET MskF_8 = BVAL(«ffffffl8» . 16) LET MskFJ) = BVAL(«fffffffO» . 16)

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

FUNCTION Or32(xA.xB)

DECLARE NUMERIC Ori, OrC

LET OrC = 0

FOR Ori=0 TO 31

LETxA = xA/2

LET xB = xB/2

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

END IF

LETxA= INT(xA)

LET xB = INT(xB)

IF (xA = 0) AND (xB = 0) THEN EXIT FOR NEXT Ori

LET Or32 = OrC

END FUNCTION

REM /'

FUNCTION And32(xA.xB) DECLARE NUMERIC Andi, AC

LET AC = 0

IF xA> MskFJTHEN

LET xA = xA - INT(xA / 4294967296) * 4294967296 END IF

IF xB > MskFJTHEN

LET xB = xB - INT(xB / 4294967296) ’ 4294967296 END IF

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

LETAnd32 = 0

ELSEIF xB = MskFJTHEN !&Hfffffffi

LET And32 = xA

ELSEIF xA= MskFJTHEN !&Hfffffffl

LETAnd32 = xB

Fl SFIF xR = MskF Я THFN ’AHffffffiR

LET And32 = INT (xA / 8) * 8

ELSEIF xA=MskF_8 THEN !&Hfffifff8

LET And32 = INT(xB / 8) ’ 8

ELSEIF xB = MskF_0 THEN !&HfffffffO

LET And32 = INT(xA /16) * 16

ELSEIF xA = MskF.O THEN ’&HfffffRO


LET And32 = INT(xB/ 16) * 16

ELSE

FOR Andi=0 TO 31

LETxA = xA/2

LETxB = xB/2

IF (INT(xA) <> xA) AND (INT(xB) <> xB) THEN

LET AC = AC ♦ 2 л Andi

END IF

LETxA = INT(xA)

LET xB - INT(*B)

IF (xA = 0) OR (xB = 0) THEN EXIT FOR

NEXT Andi

LET And32 = AC

END IF

END FUNCTION

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

FUNCTION Xor32(xA,xB)

DECLARE NUMERIC Xori, XC

LET XC = 0

FOR Xori=0 TO 31

LETxA = xA/2

LETxB = xB/2

IF ((INT(xA) = xA) AND (INT(xB) <> xB)) OR (INT(xA) о xA) AND (INT(xB) = xB) THEN LET XC = XC + 2 A Xori

END IF

LETxA = INT(xA)

LETxB = 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 Xori=Xori TO 31

LETxB = xB/2

IFINT(xB)<> xB THEN

LET XC = XC + 2 A Xori

END IF

LETxB = INT(xB) IFxB = 0THEN EXIT FOR

NEXT Xori

ELSE

FOR Xori=Xori TO 31

LETxA = xA/2

IFINT(xA) oxATHEN

LET XC = XC + 2 A Xori

END IF

LETxA = INT(xA)

IFxA = OTHEN EXIT FOR

NEXT Xori

END IF

LET Xor32 = XC

END FUNCTION

***•»•«»«•**•*»•**««*••*»<«»« »****»»e«^

FUNCTION SL32U(xA,xL)

REM 2006-05-31

DECLARE NUMERIC slAH.slAL

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

LET SL32U = xA

ELSEIF xL >=16 THEN

LET slAL = xA - INT(xA / 65536) * 65536

LET slAL = slAL * 2 A (xL • 16)

LET slAL = SlAL - INTfsIAL / 65536) ’ 65536

LET SL32U = slAL " 65536

ELSE

LET slAL = xA - INT(xA / 65536)* 65536

LET slAH - INT(xA ! 65536)

LET slAL = SlAL * 2 A xL

LET slAH = slAH ' 2 A xL

LET slAH = SlAH - INT(slAH / 65536) • 65536

LET SL32U = slAL + slAH * 65536

END 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 /...................................."""*/

FUNCTION Mul32U(xA,xB)

REM A.B : unsigned long (32-bit)

REM 2006-06-02

DECLARE NUMERIC MAH. MAL. MBH. MBL

LET MAH = I NT(xA / 65536)

LET MBH = INT(xB / 65536)

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

LET Mul32U = 0

ELSEIF (MAH = 0) AND (MBH = 0) THEN

LET Mul32U = xA * x8

ELSE

LET MAL = xA - INT(xA / 65536) * 65536

LET MBL = xB - INT(xB / 65536) * 65536

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

LET MBH = MBH - INT(MBH / 65536) * 65536

LET MAL = MAL* MBL

LET MBL = MAL - INT(MAL / 65536) * 65536

LET Mul32U = MBL ♦ 65536 * MBH

END IF

END FUNCTION

B.6 Примеры

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

Таблица В 2 — Примеры случай*» чиоел

метод генерации

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

трехпареме г ричес-кмй метел GFSR

Пягилараметри' чаский метод GFSR

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

Метод Мерсекче Теистера

Физическое случайное число

Обращение к фумсции.

Параметры

1сопдЭ2_31

«■2м.

А ■ 1 664 525.

С-1

ICOO031

• •2 100 005 341, С"0

gfor .31 Р«1 279.

9-418.

иг- 32

д1м5_31

р«521.

9»’86, *•197. *•447.

w«32

1аи$88.,Э1

Указанные а настоящем стандарте

genrand.,31

Указаыые а настоящем стандарте

гтхПаЫеЭ1

Файл pmdOI. bin

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

foil Jeong 32

inlt_IC0nj3t

Inil.glsr

Inti.gferS

inil_Uut88

lnit_georand

Inlt.mdtaNe

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

19 660 800

19 660 809

19 680 809

19 880 809

19 880 809

19 880 809

19 880 809

Результаты

Номер случайною числа

Случайное *««сло

1

2

  • 3

  • 4

  • 5

1 000

2 000

  • 3 000

  • 4 000 SOOO

1 276 136 281

865 006 703

1 408 063 416

1 021 835 442

1 313 685 521

1 292 340 048

517 257 756

1 420 573 800

1 195 033 140

971 701 120

  • 1 990 801 112

549 424 302

  • 2 128 966 934

637 203 996

965 379 446

294 652 206

407 927 492

216 557 927

919 639 774

639 093 944

716 530 710

1 004 066 693

1 271 815 862

955 533 625

626 736 765

  • 1 588 358 191

  • 2 027 766 761

1 495 802 935

1 360 928 075

1 950 421 053

716 830 710

1 004 066 893

1 271 815 862

955 533 625

626 736 785

1 935 299 389

43 896 710

  • 1 516 572 896

1923 029 091

  • 2 129 964 021

116 464 117

1 350 114 716

14 824 262

565 035 872

1 079 577 460

  • 1 404 867 807

  • 2 022 781 177

2 098 228 799

1 069 352 213

262 361 229

652 430 828

769 116 065

902 643 964

1 576 219 271

859 869 705

1 194 038 620

563 296 854

1 515 829 663

1 803 857 212

1 203 434 155

57 316 494

905 630 297

1 460 801 524

751 624 663

  • 1 289 292 436

  • 2 001 042 935

1 638 049 143

41 578 219

87 938 653

1 851 047 367


ГОСТ Р ИСО 28640—2012


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

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

Таблица ДА.1

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

Степень соответствия

Обозначение и наименование соответствующего национального стандартов

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

-

ИСО 3534-1:2006

ИСО 3534-2:2006

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

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

  • (1] ISO 80000-2 Quantities and units — Part 2: Mathematical signs and symbols to be used in the natural sciences and technology1)

  • (2] ISO/IEC 9899 Programming languages — C

  • (3] FERRENBERG A.M., LANDAU D.P. and WONG Y.J. Monte Calo Simulations: Hidden Errors from'Good* Random Number Generators. Physical Review Letters. 69(23). 1992. pp. 3382—3384

  • (4] GENTLE J.E. Random Number Generation and Monte Carlo Methods. Springer-Verlag. 2003

  • (5] HERINGA J.R., BLOTE H.W.J. and COMPAGNER A. New Primitive Trinomials of Mersenne-Exponent Degrees for Random-Number Generation. International Journal of Modem Physics C. 3(3). 1992, pp. 561—564

  • (6] ISHIDA 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] JOHNK M.D. Erzeugung Von Betavesteilten und Gammavesteilten ZufeHszahlen. Metrica, 8(1), 1964, pp. 5—15

  • (8] KNUTH D.E. Seminumerical Algorithms (The Art of Computer Programming, Volume 2), 3rd. ed.. Addison Wesley. 1998

  • (9] KURITA Y. and MATSUMOTO M. Primitive t-nomials (t = 3,5) over GF (2) Whose Degree is a Mersenne Exponent и 44497. Mathematics of Computation. 56(194), 1991. pp. 817—821

  • (10] L'ECUYER P. Maximally Equidistributed Combined Tausworthe Generators. Mathematics of Computation. 65(213), 1996. pp. 203—213

  • (11] L'ECUYER P. Tables of Maximally-Equidistributed Combined LFSR Generators. Mathematics of Computation. 68(225), 1996. pp. 261—269

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

  • (13] MASSEY J.L. Shift-Register Synthesis and BCH Decoding. IEEE Trans, on Information Theory. IT-15 (1). 1969. pp. 122—127

  • (14] MATSUMOTO M. and NISHIMURA. T. Mersenne Twister: A 623-Dimensionally Equidistributed Uniform PseudoRandom Number Generator. ACM. Trans. Model. Comput. Simul., 8(1), 1998, pp. 3—30

  • (15] VON NEUMANN J. Various Techniques Used in Connection with Random Digits, Monte Carlo Method, Applied Mathematics Series. No.12. U.S. National Bureau of Standards. Washington D.C., 1951. pp. 36—38

  • (16] 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 R.A. Analysis and Design of Stream Ciphers. Springer-Veriag. 1986

  • (19] 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. Trans. Model. Comput. Simul., 1, 1991, pp. 99—112

  • (21] VATTULAINEN I., ALA-NISSILA T. and KANKAALA, K. Physical Tests for Random Numbers in Simulations. Physical Review Letters. 73(19), 1994, pp. 2513—2516

  • (22] VATTULAINEN I.. ALA-NISSILA T. and KANKAALA, K. Physical 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.jp/random_e/index.php

Международному стандарту ISO 80000:2009 соответствует ГОСТ P 54521—2011 «Статистические методы. Математические символы и знаки для применения в стандартах».

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

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

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

Сдано в набор 23.06.2014. Подписано в печать 22.07.2014. Формат 60x84%. Бумага офсетная. Гарнитура Ариал. Печать офсетная. Усл печ. л. 4.65. Уч.-изд. л. 4.10. Тираж 40 экз Зак. 1058.

ФГУП <СТАНДАРТИНФОРМ», 123995 Москва. Гранатный пер.. 4. www.gostinfo.njinfo@gostinfo.nj

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