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

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

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

Многие вещи можно сделать и без генератора случайных чисел. Вот например, такая последовательность чисел не может считаться случайной: {0, 1, 2, 3, 4, 5, 6, 7}. Здесь, зная предыдущее число, очень легко угадать следующее. Существуют другие последовательности. Например: {0, 1, 3, 2, 6, 7, 5, 4}. Здесь, угадать следующее число значительно сложнее. Подобные последовательности иногда удобно использовать в программах. Данная последовательность определяется кодом Грея . При первом осмотре кажется что тут представлены случайные числа.

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

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

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

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

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

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

Int i; cin >> i; srand(i); // установка начального значения rand();

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

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

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

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

Диапазон значений m, при этом m > 0.
Множитель a (0 Инкрементирующее значение c (0 Начальное значение X 0 (0

Определив эти параметры, можно воспользоваться формулой:

X i+1 = (aX i + c) % m (где i больше или равно 0)

i - номер элемента в последовательности.
m - количество значений из которых формируется последовательность.
Напоминаю что % - остаток от деления

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

i max = 5; // формируем последовательность из 5 элементов
m = 10; // значения в последовательность варьируются от нуля до 9
a = 2;
c = 3;
X 0 = 6; // начальное значение (seed)

X i+1 = (2*X i + 3) % 10 (где i больше или равно 0)

X 1 = 15 % 10 = 5
X 2 = 13 % 10 = 3
X 3 = 9 % 10 = 9
X 4 = 21 % 10 = 1
X 5 = 5 % 10 = 5

Если мы увеличим последовательность, то значения начнут повторяться. Таким образом несколько неповторяющихся значений в последовательности формируют период. Период в данном примере: { 5, 3, 9, 1 }.

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

Чтобы предугадать значения элементов в последовательности можно воспользоваться формулой:

X i+k = (a*k*X i + (a*k-1)*c/b) % m (где k и i больше или равны 0)

Здесь b = a - 1. При этом a >= 2, b >= 1.

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

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

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

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

Выбор m

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

Лучше всего если бы m был равен максимальному элементу в последовательности i max +1 (единицу добавляем, так как отсчёт i идёт от нуля). Ещё одним популярным выбором является степень двойки 2 n . При условии, что n - длина машинного слова в битах, от операции взятия остатка можно избавиться. Если m является степенью двойки, То операцию взятия остатка можно заменить на более быструю операцию поразрядного И (хотя для современных компьютеров это не актуально):

X % 2 n == x & (2 n - 1)

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

X % 2 == x & 1; x % 4 == x & 3; x % 8 == x & 7;

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

Множитель a

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

Инкремент c

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

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

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

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

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

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

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

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

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

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

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

Int rnd() { int m = 10, a = 2, c = 3; static int x = x0; // x объявляется статической переменной x = ((a * x) + c) % m; // формула x0 = x; return x; }

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

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

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

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

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

Код Грея

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

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

000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7

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

000 0 001 1 011 3 010 2 110 6 111 7 101 5 100 4

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

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

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

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

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

5 && 3; // && всегда возвращает ноль или единицу (здесь 1) 5 & 3; // & возвращает число 101 011 = 001 // в результате единица То есть в данной операции сравниваются соответствующие позиции двух чисел и если они равны, то в результируюем числе в данной позиции пишется 1, в противном случае - ноль. 5 | 3; // | возвращает число 101 011 = 111 // в результате 7

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

Чтобы возвести число в какую-либо степень можно воспользоваться функцией pow(x,y). При этом Вы получите x y . Функция перегруженная, поэтому её можно использовать с разными типами. Для использования функции pow() необходимо включить заголовочный файл math.h .

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

Кроме линейного конгруэнтного генератора существует множество других. Например Вихрь Мерсенна, изобретённый двумя японскими учёными (непомню как из зовут) в 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.

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

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

k i =(a*k i-1 +b)mod c,

где а, b, с - некоторые константы , a k i-1 - предыдущее псевдослучайное число . Для получения k 1 задается начальное значение k 0 . Возьмем в качестве примера a=5,b=3,c=11 и пусть k 0 = 1 . В этом случае мы сможем по приведенной выше формуле получать значения от 0 до 10 (так как с = 11 ). Вычислим несколько элементов последовательности:

k 1 = (5 * 1 + 3) mod 11 = 8; k 2 = (5 * 8 + 3) mod 11 = 10; k 3 = (5 * 10 + 3) mod 11 = 9; k 4 = (5 * 9 + 3) mod 11 = 4; k 5 = (5 * 4 + 3) mod 11 = 1.

Полученные значения (8, 10, 9, 4, 1) выглядят похожими на случайные числа. Однако следующее значение k 6 будет снова равно 8 :

k 6 = (5 * 1 + 3) mod 11 = 8,

а значения k 7 и k 8 будут равны 10 и 9 соответственно:

k 7 = (5 * 8 + 3) mod 11 = 10; k 8 = (5 * 10 + 3) mod 11 = 9.

Выходит, наш генератор псевдослучайных чисел повторяется, порождая периодически числа 8, 10, 9, 4, 1 . К сожалению, это свойство характерно для всех линейных конгруэнтных генераторов. Изменяя значения основных параметров a, b и c , можно влиять на длину периода и на сами порождаемые значения k i . Так, например, увеличение числа с в общем случае ведет к увеличению периода. Если параметры a, b и c выбраны правильно, то генератор будет порождать случайные числа с максимальным периодом, равным c . При программной реализации значение с обычно устанавливается равным 2 b-1 или 2 b , где b - длина слова ЭВМ в битах.

Достоинством линейных конгруэнтных генераторов псевдослучайных чисел является их простота и высокая скорость получения псевдослучайных значений. Линейные конгруэнтные генераторы находят применение при решении задач моделирования и математической статистики, однако в криптографических целях их нельзя рекомендовать к использованию, так как специалисты по криптоанализу научились восстанавливать всю последовательность ПСЧ по нескольким значениям. Например, предположим, что противник может определить значения k 0 , k 1 , k 2 , k 3 . Тогда:

k 1 =(a*k 0 +b) mod c k 2 =(a*k 1 +b) mod c k 3 =(a*k 2 +b) mod c

Решив систему из этих трех уравнений, можно найти a, b и c .

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

k i =(a 1 2 *k i-1 +a 2 *k i-1 +b) mod c k i =(a 1 3 *k i-1 +a 2 2 *k i-1 +a 3 *k i-1 +b) mod c

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

Метод Фибоначчи с запаздыванием

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

Метод Фибоначчи с запаздываниями (Lagged Fibonacci Generator ) - один из методов генерации псевдослучайных чисел. Он позволяет получить более высокое "качество" псевдослучайных чисел.

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

Известны разные схемы использования метода Фибоначчи с запаздыванием. Один из широко распространённых фибоначчиевых датчиков основан на следующей рекуррентной формуле:

где k i - вещественные числа из диапазона , a, b - целые положительные числа, параметры генератора. Для работы фибоначчиеву датчику требуется знать max{a,b} предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел необходим некоторый объем памяти, зависящих от параметров a и b .

Пример . Вычислим последовательность из первых десяти чисел, генерируемую методом Фибоначчи с запаздыванием начиная с k 5 при следующих исходных данных: a = 4, b = 1, k 0 =0.1; k 1 =0.7; k 2 =0.3; k 3 =0.9; k 4 =0.5 :

k 5 = k 1 - k 4 = 0.7 - 0.5 = 0.2; k 6 = k 2 - k 5 = 0.3 - 0.2 = 0.1; k 7 = k 3 - k 6 = 0.9 - 0.1 = 0.8; k 8 = k 4 - k 7 + 1 =0.5 - 0.8 + 1 = 0.7; k 9 = k 5 - k 8 + 1 =0.2 - 0.7 + 1 = 0.5; k 10 = k 6 - k 9 + 1 =0.1 - 0.5 + 1 = 0.6; k 11 = k 7 - k 10 = 0.8 - 0.6 = 0.2; k 12 = k 8 - k 11 = 0.7 - 0.2 = 0.5; k 13 = k 9 - k 12 + 1 =0.5 - 0.5 + 1 = 1; k 14 = k 10 - k 13 + 1 =0.6 - 1 + 1 = 0.6.

Видим, что генерируемая последовательность чисел внешне похожа на случайную. И действительно, исследования подтверждают, что получаемые случайные числа обладают хорошими статистическими свойствами.(a,b) = (17,5) рекомендуются для простых приложений. Значения (a,b) = (55,24) позволяют получать числа, удовлетворительные для большинства криптографических алгоритмов, требовательных к качеству случайных чисел. Значения (a,b) = (97,33) позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности.

Генераторы ПСЧ, основанные на методе Фибоначчи с запаздыванием, использовались для целей криптографии. Кроме того, они применяются в математических и статистических расчетах, а также при моделировании случайных процессов. Генератор ПСЧ, построенный на основе метода Фибоначчи с запаздыванием, использовался в широко известной системе Matlab.

Следующий большой шаг в разработке генераторов случайных чисел был сделан Д. Лемером (D.H. Lehmer) в 1949 году. Предложенный им генератор носит название линейного конгруэнтного метода (linear congruential method). Выберите три числа т, а и с и начальное число Х0. Для генерации последовательности случайных чисел используется следующая формула:

Хл+і = (аХ„ + с) mod т

Операция взятия по модулю т (mod т) представляет собой вычисление остатка от деления числа на т, например, 24 mod 10 = 4.

При удачном выборе начальных чисел генерируемая последовательность будет содержать случайные числа. Например, стандартный генератор случайных чисел в Delphi использует значения а = 134775813 ($8088405), с = 1 и т = 232, а значение Х0 выбирается самим пользователем. (Значение начального числа содержится в глобальной переменной RandSeed. Его можно задавать напрямую или использовать процедуру Randomize для вычисления его на основе показаний системных часов.) Следует отметить, что если в двух разных точках последовательности получено одно и то же значение х, то последовательность в этих двух точках должна полностью повторяться, поскольку алгоритм детерминированный. Так как в формуле используется операция определения остатка от деления, все значения в последовательности будут меньше га, т.е. будут находиться в диапазоне от 0 до т-1. Следовательно, последовательность будет повторяться после не более чем т чисел. При неудачном выборе значения а, с и т повторение последовательности может начаться гораздо раньше. В качестве простого примера можно привести случай, когда а = 0: вся последовательность сводится к повторению значения параметра с -

Каким образом можно выбрать удачные значения для а, с и ті В литературе содержится немало размышлений, описаний и доказательств. Как правило, значение параметра т выбирается как можно больше, чтобы цикл повторяемости был также как можно большим. Нужно выбирать его, как минимум, равным размеру слова операционной системы (другими словами, для 32-разрядных операционных систем т выбирается равным 31 или 32 бита). Значение параметра а выбирается таким образом, чтобы оно было взаимно простым со значением числа т (два числа являются взаимно простыми, если их наибольший общий делитель равен 1). Значение с, как правило, берется равным 0 или 1, несмотря на то, что общее правило гласит, что должно выбираться ненулевое значение, взаимно простое со значением параметра т.

В случае если значение с равно 0, генератор называется мультипликативным линейным конгруэнтным генератором случайных чисел (multiplicative linear congruential generator). Чтобы гарантировать, что цикл повторения последовательности максимален, необходимо в качестве значения параметра т выбирать простое число. Самым известным генератором подобного рода является так называемый минимальный стандартный генератор случайных чисел (minimal standard random number generator), предложенный Стивеном Парком (Stephen Park) и Кей-том Миллером (Keith Miller) в 1988 году. Для него а = 16807, а т = 2147483647 (или 231 - 1). После разработки этого генератора было проведено большое количество статистических тестов, и генератор прошел большинство из них (несмотря на то что предложенный генератор обладает определенными нежелательными свойствами, которые мы рассмотрим чуть ниже).

Мультипликативные линейные конгруэнтные генераторы случайных чисел имеют одну аномалию: они никогда не дают числа 0. (Это объясняется тем, что, во-первых, т представляет собой простое число, во-вторых, a mod т не равно нулю, и, в-третьих, если начальное число не равно нулю, Х0 mod т тоже не равно нулю.) Следовательно, если генераторы никогда не дают числа 0, их нельзя назвать случайными. На практике невозможность генерации нуля, как правило, игнорируется, - в конце концов, в 32-разрядной операционной системе это всего лишь отсутствие всего одного числа из примерно 2 миллиардов.

При реализации минимального стандартного генератора случайных чисел (как, в общем-то, и любого другого) особое внимание необходимо уделить исключению возможности возникновения переполнения, поскольку значение текущего начального числа, умноженное на а, может легко превысить максимально допустимое значение для 32-битного целого числа. Если не позаботиться об исключении переполнения, возможно возникновение ошибок, которые негативно скажутся на достаточно хорошем генераторе случайных чисел. Для обработки случаев переполнения используется метод Шрейга (Schräge) (его описание в этой книге не приводится, но его можно найти в статье Парка и Миллера ).

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

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

Листинг 6.2. Базовый класс генератора случайных чисел

Type TtdBasePRNG = class private FName: TtdNameString; protected procedure bError(aErrorCode: integer; const aMethodName: TtdNameString); public function As Double: double; virtual; abstract;

{-вернуть случайное число из диапазона от 0 включительно до 1

Исключительно} function AsLimitedDouble(aLower, aUpper: double) : double; {-вернуть случайное число из диапазона от aLower включительно до aUpper исключительно} function As Integer (aUpper: integer) : integer; {-вернуть случайное число из диапазона от 0 включительно до aUpper исключительно} property Name: TtdNameString read FName write FName; end; function TtdBasePRNG.AsLimitedDouble(aLower, aUpper: double) : double; begin if (aLower < 0.0) or (aUpper < 0.0) or (aLower >= aUpper) then bError(tdeRandRangeError, 1 AsLimitedDouble"); Result:= (AsDouble * (aUpper - aLower)) + aLower; end; function TtdBasePRNG. As Integer (aUpper: integer) : integer; begin if (aUpper <= 0) then bError(tdeRandRangeError, "AsInteger"); Result:= Trunc(AsDouble * aUpper) ; end; procedure TtdBasePRNG. bError (aErrorCode: integers-const aMethodName: TtdNameString); begin raise EtdRandGenException. Create (FmtLoadStr(aErrorCode, )) ; end;

В листинге 6.2 приведен код базового класса генератора случайных чисел. В нем определен виртуальный метод AsDouble, который возвращает случайное число х в диапазоне 0<х< 1. Кроме того, в классе объявлены два простых метода, один из которых возвращает случайное число с плавающей запятой из заданного диапазона значений, а второй - из диапазона значений от 0 до некоторой заданной верхней границы (аналогично тому, как функция Random (Limit) использует целое значение Limit). Теперь, когда базовый класс определен, для реализации алгоритма Парка и Миллера можно объявить дочерний класс.

Листинг 6.3. Минимальный стандартный генератор псевдослучайных чисел

Type TtdMinStandardPRNG = class (TtdBasePRNG) private FSeed: longint; protected procedure msSetSeed(aValue: longint); public constructor Create(aSeed: longint); function AsDouble: double; override; property Seed: longint read FSeed write msSetSeed; end; constructor TtdMinStandardPRNG. Create (aSeed: longint); begin inherited Create; Seed:= aSeed; end;

function TtdMinStandardPRNG.AsDouble: double; const

A = 16807; m = 2147483647; q= 127773; {равно m diva} r = 2836; {равно m mod a} OneOverM: double = 1.0V / 2147483647.0; var k: longint; begin k:= FSeed div q; FSeed:= (a * (FSeed - (k * q))) - (k * r) ; if (FSeed <= 0) then inc(FSeed, m) ; Result:= FSeed * OneOverM; end; function GetTimeAsLong: longint; {$IFDEF Delphi 1} assembler; asm

Call DOS3Call mov ax, cx end; {$ENDIF] {$IFDEF Delph±2Plus) begin Result:= longint(GetTickCount); end; {$ENDIF) {$IFDEF KylixlPlus) var T: TTime_t; begin _time(@T); Result:= longint(T); end;

{$ENDIF) procedure TtdMinStandardPRNG.ms Set Seed (aValue: longint); const

m = 2147483647; begin if (aValue > 0) then FSeed: = aValue

else FSeed:= GetTimeAsLong; {убедиться, что значение начального числа находится в переделах от 0 до т-1

Включительно} if (FSeed >=m-l) then FSeed:= FSeed - (m - 1) + 1; end;

Как несложно заметить в коде метода AsDouble, метод Шрейга выглядит гораздо сложнее, нежели простая формула Xn+l = aXn mod т со значениями а = 16807 и т = 231- 1. Тем не менее, используя достаточно сложные математические выкладки, можно доказать его равенство приведенной формуле.

Кроме того, как уже упоминалось, в генераторе случайных чисел подобного типа использование нуля в качестве начального числа нежелательно, поскольку тогда бы все генерируемые значения были бы нулевыми. Поэтому метод msSetSeed использует значение 0 в качестве флага при необходимости установки начального числа по значению системных часов. К сожалению, для выполнения этой операции в 16- и 32-разрядных системах Windows используется разный код.

Создадим класс случайных чисел, который будет использовать системный генератор случайных чисел - функцию Random. В листинге 6.4 показан код метода AsDouble для такого класса.

Листинг 6.4. Использование в классе системной функции Random

Function TtdSystemPRNG.AsDouble: double; var OldSeed: longint; begin OldSeed:= System.RandSeed; System.RandSeed:= Seed; Result:= System.Random; Seed:= System. RandSeed ; System.RandSeed: = OldSeed; end;

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

Но как я могу обеспечить, чтобы все случайные числовые потоки имели это максимальное свойство? Что касается MPI, как мне включить rank и size для создания максимальных периодов с использованием линейного конгруэнтного метода? Было бы проще использовать Lagged Fibonacci или Mersenne Twister для создания более длинных параллельных случайных потоков?

8

4 ответы

Существует очень хорошая обзорная обзорная статья Katzgrabber, Случайные числа в научных вычислениях: введение , в котором я указываю людям, кто хочет быть пользователь PRNG для научных вычислений. Линейные конгруэнтные генераторы бывают быстрыми, но это все, что у них есть для них; у них короткие периоды, и они могут легко ошибиться; вполне разумно выглядящие комбинации a, c и m могут заканчиваться ужасно коррелированными выходами, даже если вы удовлетворяете обычным требованиям между a, c и m.

Хуже того, в одном общем случае, когда m является степенью двух (поэтому операция mod быстро), биты более низкого порядка имеют гораздо более короткий период, чем последовательность в целом, поэтому, если вы выполняете rand ()% N, у вас есть еще более короткий период, чем вы ожидали.

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

С точки зрения посева параллельно метод Джека Поулсона хорош, потому что он дает четко определенную последовательность чисел, равномерно распределенных между процессорами. Если это не имеет значения, вы можете сделать все возможное, чтобы засеять различные ПРНГ; в той же самой статье говорится о том, что многие люди придумали независимость, хешируя номер задачи PID или MPI со временем. Конкретная формула, предложенная там

Long seedgen(void) { long s, seed, pid; pid = getpid(); s = time (&seconds); seed = abs(((s*181)*((pid-83)*359))%104729); return seed; }

У меня нет особых мнений об этой конкретной реализации, но общий подход, безусловно, разумный.

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

Это работает, потому что для RNG, которые не вычисляют все это (LCG, безусловно, один, но многие другие должны быть в этой категории), реальное узкое место отправляет семена в память (а также, возможно, последующую обработку). Если вы запускаете LCG, не отправляя ничего в память, все это должно оставаться в регистрах CPU и быть очень быстрым. Даже для более сложного RNG вы должны оставаться в кеше L1 и быть очень быстрым.

Я использовал этот очень простой подход с LCG, который по старым причинам мы должны сохранить. В основном мы получаем линейное ускорение до потоков 4-8 на типичной многоядерной рабочей станции. Но теперь я попробую метод от ответа Джека Поулсона и надеюсь, что он будет еще быстрее:).

OTOH, я считаю, что этот простой трюк должен работать для других неотъемлемых последовательных ГСЧ.