Меню

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



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

Дата создания: 2009-05-03 15:27:38
Последний раз редактировалось: 2012-02-08 06:53:25

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

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

Генерация псевдослучайных чисел

Обычно используется генерация псевдослучайных чисел. Т.е. числа не совсем случайные. Мы уже рассматривали функцию rand(). Если Вы напишите программу использующую данную функцию, то при каждом запуске программы, rand() будет генерировать одну и ту же последовательность чисел. Последовательность сгенерированная rand() определяется начальным числом (seed). Сначала задаётся начальное число, затем, по определённой формуле вичисляются все остальные числа последовательности. Зная начальное число и формулу по которой рассчитываются числа, можно вычислить следующее число.

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

Одним из предопределённых (детерминистических) алгоритмов создания случайных чисел является линейно-конгруэнтный.

Установка начального значения (для функции rand(), которую мы использовали до сих пор) выглядит примерно так:

Функция srnd устанавливает начальное значение i.

Линейный конгруэнтный (linear congruential) метод генерации случайных чисел

Существует много методов генерации случайных чисел. Линейно-конгруэнтный лишь один из них. Метод довольно старый — 1950х годов. Разработал его Деррик Лемер.

Для реализации алгоритма необходиом задать четыре параметра:

Диапазон значений m, при этом m > 0.
Множитель a (0 = 2, b >= 1.

Вичислим шестой элемент с помощью этой формулы (мы ведь уже знаем пятый):

X5+1 = (a*1*X5 + (a*1-1)*c/b) % m = (2*1*5 + (2*1-1)*3/1) % 10 = 13 % 10 = 3

Всё росто, правда?

У последовательности созданной с помощью линейного конгруэнтного метода и определённой целыми параметрами m, a, c и X, период равен числу m когда выполняются следующие условия:
1.Наибольший общий делитель c и m равен 1.
2.b — кратно любому простому числу, являющемуся делителем m.
3.Если m кратно 4, тогда b также кратно 4.

Выбор m

Период не может быть больше числа m. Следовательно m должно быть довольно большим.

Примеры (x — целое число):

Очень часто для m выбирают одно из простых чисел Мерсенна [3] . Часто число 2 31 — 1 используется, когда вычисления ведутся с 32-ух битными данными.

Множитель a

Множитель нужно выбирать так, чтобы период был как можно длиннее. Существует серьёзная проблема с данным коэффициентом: при малых значениях a, если текущий элемент последовательности достаточно мал, вполне вероятно, что следующий элемент тоже будет маленьким.

Инкремент c

Данный параметр можно выбирать довольно произвольно. Очень часто его задают в виде нуля, но при этом уменьшается длина периода и X != 0.

Начальное значение (seed)

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

Вот так вот! Генерация последовательных чисел — это самая настоящая мистификация!

Т.е. у нас допустим есть генератор случайных чисел. Мы его используем для разных программ. Всегда, всегда этот генератор создаёт одинаковую последовательность чисел (при одинаковых начальных значениях). Мы можем только установить начальное значение.

Вообще говоря, с помощью арифметических методов нельзя построить по настоящему случайную последовательность чисел. Как невесело шутил наш друг — Джон Фон Нейман:

«Anyone who uses arithmetic methods to produce random numbers is in a state of sin.» (C) Джон Фон Нейман.

Грустно всё это. Вот так живёшь-живёшь. Находясь в состоянии неведения, думаешь: «А вот круто бы было создать генератор случайных чисел на основе линейного когнруэнтного метода!». А оказывается что по настоящему случайную последовательность таким образом создать нельзя. Крах надежд! Депрессия и вот ты уже на пороге первой стадии алкоголизма. Этот груз невозможности реализовать свои желания будет давить на тебя всю оставшуюся жизнь. Что-то я отвлёкся. Продолжим.

Читайте также:  Установка выносного регулятора генератора

Реализация генерации случайных чисел

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

Для последовательности рассмотренной выше, генератор будет выглядеть так:

X объявляется как глобальная переменная:

Это самый примитивный вариант генератора. В реальности такое чудовище использовать нельзя! Но мы будем это делать!

В данной реализации мы никак не отслеживаем возможность переполнения переменных. Вместо типа int используйте тип _int64 — это целый восьмибайтный тип.

Простые числа

Простые числа — числа которые можно разделить без остатка только на единицу и на само число. Например: 11, 3, 7.

Код Грея

[1] Код Грея представляет собой последовательность чисел, где следующее число отличается от предыдущей одним битом. Т.е. чтобы угадать последовательность, нужно смотреть не на десятичные числа, а на их двоичные эквиваленты.

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

Используя код Грея, получим такую последовательность:

Простые числа Мерсенна

[3] На данный момент известно 44 числа Мерсенна. Из названия понятно, что данные числа — простые, т.е. делятся только на единицу и на самих себя. Кроме того данные числа должны подчиняться следующей формуле:

Где n также простое число. Для первых девяти простых чисел Мерсенна n следующие: <2, 3, 5, 7, 13, 17, 19, 31, 61>.

Поразрядные логические операции

[2] Мы уже рассматривали логические операции && (И) и || (ИЛИ). Существуют также поразрядные логические операции & (поразрядное И) и | (поразрядное ИЛИ). Работате операция следующим образом:

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

Степень числа

Другие генераторы случайных чисел

Кроме линейного конгруэнтного генератора существует множество других. Например Вихрь Мерсенна, изобретённый двумя японскими учёными (непомню как из зовут) в 1997. У него очень большой (очень большой это мягко сказано) период. Кстати, вихрь Мерсенна использует линейный конгруэнтный генератор для установления начального значения (seed).

Генераторы случайных чисел применяются при шифровании. Но здесь используются специальные генераторы — криптографически защищённые генераторы псевдослучайных чисел. Например блочный шифр (block cipher), потоковый шифр (stream cipher), который был разработан на основе шифра Вернама.

Упражнения:

Реализуйте генераторы случайных чисел на основе линейного когруэнтного метода. В качестве параметров воспользуйтесь следующими:

  • m = 2 32 ; a = 1664525; c = 1013904223. Данные параметры использовались в примере реализации генератора в одной старой книжке по Фортрану.
  • m = 2 32 ; a= 214013; c = 2531011; Данные параметры используется в реализации метода в Visual C++. При этом берутся старшие биты 30..16. Берутся именно верхние биты, т.к. в линейном конгруэнтном методе нижние биты гораздо менее случайны. Так как мы пока не умеем брать конкретные биты, можете использовать всё число.
  • В качестве m выберите одно из чисел Мерсенна. Начните с малых (2 3 -1,2 5 -1). Попробуйте подставить 2 31 -1 и 2 61 -1.

Данный материал поможет вам понять как работают генераторы случайных чисел. К этому материалу будет продолжение: мы напишем нормальный генератор и рассмотрим различные приёмы работы с генераторами псевдослучайных чисел.

Источник

Глава 2. Моделирование случайных событий

2.1.Единичный жребий

Имитация функционирования стохастической системы на ЭВМ заключается в многократном прогоне модели системы. Результатом однократного прогона является одна реализация моделируемого процесса (явления). Реализация — это один экземпляр процесса. Реализации отличаются друг от друга за счет случайностей. Отдельная реализация случайного явления разыгрывается при помощи специального алгоритма, важную роль, в котором играет процедура «бросания жребия». Каждый раз, когда в ход процесса вмешивается случай, его влияние учитывается не расчетом, а жеребьевкой. Именно этим имитационное моделирование принципиально отличается от аналитического. К жеребьевке в имитационном моделировании прибегают каждый раз, когда дальнейшее развитие процесса (а значит и его результата) зависит от того, произошло или нет какое-то событие. Например, попал ли снаряд в цель, исправна ли аппаратура, устранена ли неисправность и т.п. Кроме случайных событий на ход и исход процесса могут влиять различного рода случайные величины, например, стартовая масса ракеты, толщина листового проката, пределы прочности и др. С помощью жребия можно разыграть значение любой случайной величины, любого случайного вектора.

Читайте также:  Все генераторы из тепловозов

Жеребьевка при помощи ЭВМ имеет свою специфику. Здесь не пригодны тиражные барабаны, лототроны и даже электронные генераторы из-за их низкой производительности. Для этой цели применяют специальные программные генераторы случайных величин. Величины, получаемые при помощи программы, конечно, не являются действительно случайными, но обладают многими свойствами случайных величин. Поэтому они называются псевдослучайными.

Основой для моделирования случайных событий и случайных величин с различными законами распределения служит базовая случайная величина, равномерно распределенная в интервале (0,1). Программные генераторы псевдослучайных величин используют рекуррентные математические методы, позволяющие каждое новое число получать из одного или нескольких предыдущих.

2.2.Базовая случайная величина

Так называется случайная величина, распределенная равномерно в интервале от 0 до 1. Обозначим ее символом R. Плотность распределения f(r) базовой случайной величины такова

Математическое ожидание и дисперсия базовой случайной величины соответственно равны

2.3.Мультипликативный конгруэнтный генератор базовой случайной величины

Два целых числа A и B конгруэнтны (сравнимы) по модулю M, если их разность делится на M без остатка. То есть

A — B = k M,

где k — целое. Это определение записывается так

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

где a и M положительные целые числа. Согласно этому выражению, для получения очередного числа следует взять последнее число, умножить его на постоянный множитель a, разделить на M и остаток приравнять. Иначе

(2.1)

где k выбирается так, чтобы

В алгоритмических языках программирования (Фортран, Паскаль) существует встроенная функция mod, выполняющая эту операцию.

График функции (2.1) изображен на рис. 2.1. От выбора a и M зависят статистические свойства программы — генератора. В качестве модуля M обычно выбирают максимально возможное целое число. При 32-разрядном двоичном коде это число равно Такой выбор обеспечивает наибольший период. Хорошие статистические свойства последовательности псевдослучайных чисел обеспечивается выбором a и стартового числа. Множитель a не должен быть каким-либо образом связан с модулем M. При

указанном значении M хорошие результаты получаются со следующими a: 16807, 477 211 307, 1 220 703 125, 6 469 693 231. В качестве следует использовать большое целое нечетное число.

Для того чтобы из получить величину, заключенную в интервале (0,1) достаточноразделить на модуль M. Наиболее распространенная программа-генератор (на Фортране) значений базовой псевдослучайной величины выглядит так.

Subroutin Randu (ix, iy, R)

iy = ix * 1 220 703 125

3 iy = iy + 2 147 483 647 + 1

4 R = iy * 0.4656613e-9

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

Статистические свойства генераторов псевдослучайных величин проверяются при помощи многочисленных тестов. Так для проверки равномерности распределения единичный квадрат (куб, гиперкуб) разбивается (произвольно) на m частей с площадями (объемами) , так что сумма площадей равна единице. Затем генерируется 2N (в случае квадрата) чисел, из которых образуется N пар

Каждая пара представляет собой точку в квадрате. Если в каждой части квадрата окажется точек, частоты попадания точек равны

Принадлежность частот q распределению p проверяется одним из критериев согласия, например, критерием Пирсона.

Для проверки независимости друг от друга последовательно сгенерированных чисел, вычисляется оценка ковариации лага s:

Эта оценка должна мало отличаться от нуля для всех s, кроме s=0. Для больших N с вероятностью 99.73% статистика

должна быть заключена в интервале

Источник

Глава 2. Моделирование случайных событий

2.1.Единичный жребий

Имитация функционирования стохастической системы на ЭВМ заключается в многократном прогоне модели системы. Результатом однократного прогона является одна реализация моделируемого процесса (явления). Реализация — это один экземпляр процесса. Реализации отличаются друг от друга за счет случайностей. Отдельная реализация случайного явления разыгрывается при помощи специального алгоритма, важную роль, в котором играет процедура «бросания жребия». Каждый раз, когда в ход процесса вмешивается случай, его влияние учитывается не расчетом, а жеребьевкой. Именно этим имитационное моделирование принципиально отличается от аналитического. К жеребьевке в имитационном моделировании прибегают каждый раз, когда дальнейшее развитие процесса (а значит и его результата) зависит от того, произошло или нет какое-то событие. Например, попал ли снаряд в цель, исправна ли аппаратура, устранена ли неисправность и т.п. Кроме случайных событий на ход и исход процесса могут влиять различного рода случайные величины, например, стартовая масса ракеты, толщина листового проката, пределы прочности и др. С помощью жребия можно разыграть значение любой случайной величины, любого случайного вектора.

Читайте также:  Kia optima гибрид генератор

Жеребьевка при помощи ЭВМ имеет свою специфику. Здесь не пригодны тиражные барабаны, лототроны и даже электронные генераторы из-за их низкой производительности. Для этой цели применяют специальные программные генераторы случайных величин. Величины, получаемые при помощи программы, конечно, не являются действительно случайными, но обладают многими свойствами случайных величин. Поэтому они называются псевдослучайными.

Основой для моделирования случайных событий и случайных величин с различными законами распределения служит базовая случайная величина, равномерно распределенная в интервале (0,1). Программные генераторы псевдослучайных величин используют рекуррентные математические методы, позволяющие каждое новое число получать из одного или нескольких предыдущих.

2.2.Базовая случайная величина

Так называется случайная величина, распределенная равномерно в интервале от 0 до 1. Обозначим ее символом R. Плотность распределения f(r) базовой случайной величины такова

Математическое ожидание и дисперсия базовой случайной величины соответственно равны

2.3.Мультипликативный конгруэнтный генератор базовой случайной величины

Два целых числа A и B конгруэнтны (сравнимы) по модулю M, если их разность делится на M без остатка. То есть

A — B = k M,

где k — целое. Это определение записывается так

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

где a и M положительные целые числа. Согласно этому выражению, для получения очередного числа следует взять последнее число, умножить его на постоянный множитель a, разделить на M и остаток приравнять. Иначе

(2.1)

где k выбирается так, чтобы

В алгоритмических языках программирования (Фортран, Паскаль) существует встроенная функция mod, выполняющая эту операцию.

График функции (2.1) изображен на рис. 2.1. От выбора a и M зависят статистические свойства программы — генератора. В качестве модуля M обычно выбирают максимально возможное целое число. При 32-разрядном двоичном коде это число равно Такой выбор обеспечивает наибольший период. Хорошие статистические свойства последовательности псевдослучайных чисел обеспечивается выбором a и стартового числа. Множитель a не должен быть каким-либо образом связан с модулем M. При

указанном значении M хорошие результаты получаются со следующими a: 16807, 477 211 307, 1 220 703 125, 6 469 693 231. В качестве следует использовать большое целое нечетное число.

Для того чтобы из получить величину, заключенную в интервале (0,1) достаточноразделить на модуль M. Наиболее распространенная программа-генератор (на Фортране) значений базовой псевдослучайной величины выглядит так.

Subroutin Randu (ix, iy, R)

iy = ix * 1 220 703 125

3 iy = iy + 2 147 483 647 + 1

4 R = iy * 0.4656613e-9

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

Статистические свойства генераторов псевдослучайных величин проверяются при помощи многочисленных тестов. Так для проверки равномерности распределения единичный квадрат (куб, гиперкуб) разбивается (произвольно) на m частей с площадями (объемами) , так что сумма площадей равна единице. Затем генерируется 2N (в случае квадрата) чисел, из которых образуется N пар

Каждая пара представляет собой точку в квадрате. Если в каждой части квадрата окажется точек, частоты попадания точек равны

Принадлежность частот q распределению p проверяется одним из критериев согласия, например, критерием Пирсона.

Для проверки независимости друг от друга последовательно сгенерированных чисел, вычисляется оценка ковариации лага s:

Эта оценка должна мало отличаться от нуля для всех s, кроме s=0. Для больших N с вероятностью 99.73% статистика

Z = 0.5 ln((1 + K)/(1 — K))

должна быть заключена в интервале

Источник