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

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

СТАНДАРТ

РОССИЙСКОЙ

ФЕДЕРАЦИИ

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

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.ru)

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

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

ГОСТ Р ИСО 28640-2012

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

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

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

где b > 0.

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

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

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

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

1

-ехр {-(у~а)1 Ь}, у >а Ь

о,    у<а’

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

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

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

У = -b\r\(U) + а.

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

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

f(^z) = -/==ехр]-—V(^z-I^x)² r>

<j2nc L 2сг J

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

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

Если стандартные равномерные случайные числа U₁ и U₂ независимо генерированы методом, установленным в 6.2.1, то два независимых нормальных случайных числа Z_b Z₂ получают в соответствии со следующей процедурой

Z., = д + о д/-2ln(1-l/.|) cos (2kU₂),

Z₂- д + о J-2ln(1-l/.|) sin (2kU₂).

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

псевдослучайных стандартных нормальных величин является м = ^/-2ln(m^-1) =^/2lnm ■ Таким образом, если

т = 2³², то М ~ 6,6604, а если т = (2³¹ - 1), то М ~ 6,5555. Однако, так как вероятность того, что абсолютные значения случайных величин истинного стандартного нормального распределения, превышающих М, приблизительно равна Ю“¹⁰’, это редко создает трудности на практике.

Примечание 2 — При получении U-\, U₂ линейным конгруэнтным методом последовательно, U-\ и U₂ являются зависимыми, таким образом хвост распределений, полученных Z-| и Z₂, может существенно отличаться от истинного нормального распределения.

7

ГОСТ Р ИСО 28640-2012

d)    Генерируют стандартное равномерное случайное число l/и вычисляют V- (л+1)1/.

e)    Вычисляют к - L\/J и и = V- к, где LvJ — целая часть числа V.

f)    Если и < v_k, то Y - к; в противном случае Y - а_к.

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

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

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

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

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

Генерируют стандартные равномерные случайные числа U_b U₂,.... В качестве У используют максимальное значение п, удовлетворяющее следующему неравенству

-1п{(1-У₁)(1-У₂)...(1-и„)}<д.

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

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

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

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

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

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

2^kЛ+^ <N-M+ \<2^к.

Примечание1 — Величина к — наименьшее натуральное число, удовлетворяющее неравенству к> \og₂(N - М + 1).

Пример 1 — Если (N - М + 1) = 100, то к =7, поскольку(2⁶ + 1) = 65 й 100 < 2⁷ = 128.

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

Примечание2 — к- битовое двоичное число Z₁Z₂Z₃Z₄...Z^ соответствует десятичному числу 2^^_1 Z-, + 2^k~²Z₂ + 2^k~³Z₃ + 2^Z₄ + ... + Z_k.

Пример 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.2.

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

11

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

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

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

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

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

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

ГОСТ Р ИСО 28640-2012

Например, для аналогово-цифрового преобразования может быть использован конвертер DAS-41024 У этого оборудования разрешающая способность составляет 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. (информация дана только для удобства пользователей настоящего стандарта).

13

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

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

Ниже приведен текст программы на языке Си, которая в соответствии с ИСО/МЭК 9899 является примером метода GFSR с параметрами (р, q, w) = (1279, 418, 32) и периодом (2¹²⁷⁹ - 1). При обращении к функции gfsr () происходит генерация целого числа из интервала от 0 до (2³² - 1) включительно. При обращении к функции gfsr_31 () происходит генерация целого числа из интервала от 0 до (2³¹ - 1) включительно. Для обращения к функциям gfsr () и gfsr_31 () необходима единственная инициализация initgfsr (s). Функция init_gfsr (s) выполняет инициализацию при условии, что в качестве начального числа используется 32-битовое целое число без знака [целое число из интервала от 0 до (2³² - 1)]. Полученная последовательность обеспечивает 39 независимых серий псевдослучайных чисел, каждая из которых обладает незначительной автокорреляцией, имеет 39-мерное распределение (однородно распределена в 39-мерном гиперкубе) с 32-битовой точностью, и ее функция автокорреляции такова, что значения близкие к нулю появляются через 2¹²⁷⁴ чисел.

Чтобы получить другую последовательность псевдослучайных чисел, необходимо изменить начальное число s в функции init_gfsr (s). В программе могут быть изменены только константы р, q, w. Значение w должно быть

равно 2 в целой степени в соответствии с длиной слова машины. Значение w, в общем случае, равно 32 или 64 в зависимости от возможностей машины. Например, если длина слова машины 64, постоянную w в программе устанавливают равной 64, а функция gfsr () генерирует целые числа из интервала от 0 до (2⁶⁴ — 1) включительно, в то время как функция gfsr_31 () генерирует целые числа из интервала от 0 до (2⁶³ — 1) включительно.

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

^*************************************************

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

************************************************* j

#define Р 1279 #define Q 418

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

static unsigned long state [P] ;

static int state J ;

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 [i] |= x [k]; x [k] ^Л= x [ (k+Q) %P]; k++;

if (k==P) k = 0 ;

}

}

statej = 0 ;

}

unsigned long gfsr (void)

{

int i;

ГОСТ Р ИСО 28640-2012

Содержание

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

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

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

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

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

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

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

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

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

ссылочным национальным стандартам Российской Федерации........... 34

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

Введение

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

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

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

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

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

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

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

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

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

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

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

IV

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

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

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 (m; к) — остаток от деления целого числа т на целое число к;

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

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

ОФ 1 = 1,

1Ф 0 = 1,

0Ф0 = 0.

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

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

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

0    л 1=0,

1    л 0 = 0,

О л 0 = 0.

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

т := к — замена значения т на значение /с;

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

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

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

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

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

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

2

ГОСТ Р ИСО 28640-2012

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

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

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

х_п+р = S-1 Vi ⁺ СР-2 W2 ⁺ - ^{+ С}1 ^хп+1 ⁺ ХП (mod 2) (л = 1,2, 3, ...).

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

c)    Полином

t^p + с_р_1 t^p-¹ + ... + с₁₍ + 1 является характеристическим полиномом для приведенной выше рекуррентной формулы.

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

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

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

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

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

Хр+р ⁼ X_n+i© X_n+q₂ © Х_п+р^ ® Х_п(П -1,2, 3...).

Параметры (р, q_b q₂, q₃, w) и Х_ь ..., Х_р первоначально задают как начальные числа. Примеры параметров р, q_b q₂, q₃ с наибольшим периодом (2^Р - 1) приведены в таблице 1.

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

p Ф <?2 <Ь 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 Примечание — <7i> <7г> <7з являются показателями степени ненулевых членов характеристического полинома.

^ GFSR — Generalized Feedback Shift Register.

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

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

х_п+р = (x_n+q + х„) (mod 2), (л = 0,1,2,...),

где х₀, х_ьх₂,... — соответствующая М-последовательность.

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

^— x_nf x_nf₊i... х_п^ _+и^1, (л — 0, 1,2, ...),

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

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

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

Пример — Если в качестве исходного выбран многочлен t²+1 +1, установлены параметры р=4 и q=1 и в приведенной выше рекуррентной формуле заданы начальные числа (х₀,х₁,х₂,х₃) = (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) имеет вид

Х₀ =х₀х₁х₂х₃ = 1111 (= 15),

Х₁ =х₄х₅х₆х₇ = 0001 (= 1), ^х2 = ^х8 х_а х₁₀ Хц = 0011 (= 3),

Х₃ = х₁₂ х₁₃ х₁₄ х₀ = 0101 (= 5),

Х₄ = х, х₂ х₃ х₄ = 1110 (= 14),

Х₅ = х₅ х₆ х₇ х₈ = 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, комбинированный метод Таусворта генерирует последовательность псевдослучайных чисел {Х_п} как результат побитовой операции «исключающее ИЛИ» при двоичном представлении чисел в этих J последовательностях.

Х_П = Х^_П ©Х⁽²⁾п ® ... ®X<^J)n in — 0, 1, 2, ...).

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

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

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

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

X_n+p = X_n+q ® (X^fn\Х\₊,Р А, (л = 1,2, 3, ...),

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

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

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

{X^fn\X'^[n^f^r) — двоичное целое число, полученное конкатенацией чисел X^fn и Х^_п+^, когда первые (w-r) битов взяты изХ„, а последние г битов из (Х_п+1) в том же порядке;

ГОСТ Р ИСО 28640-2012

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

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

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

У
У	-у®	(у»	и),
У	-у®	[(у «	S) А Ь],
У	-у®	[(у «	f) A С],
У	-у®	(У»	/).

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

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

Параметрами этого алгоритма являются (р, q, г, w, а, и, s, t, I, b, с). Начальными числами являются Х₂,..., X_q+1 и первые (w-r) битов числа X,.

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

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

6.1    Введение

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

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

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

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

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

И / Ь, если а < у < а + b [О, если у g [а, а + Ь] ’

где Ь > 0.

5

1

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

2