Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Генератор псевдослучайных чисел Mersenne Twister




Читайте также:
  1. DDS генератор
  2. А) Проверка работоспособности статора генератора
  3. Автогенератор на операционном усилителе
  4. Автогенераторы гармонических колебаний
  5. В ходе изучения чисел, которые выбрала моя подруга, мы установили, что она приняла убеждение о том, что ей никогда не получить то, чего она действительно хочет.
  6. Возбудители генераторов и ГЭД
  7. Выбор ваших чисел
  8. ГЕНЕРАТОР SIGLENT SDS 1000DL
  9. Генератор отчетов

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

В качестве наглядного примера, рассмотрим сначала один из простейших генераторов псевдослучайных чисел – метод середины квадратов, предложенный Дж. Нейманом в 1946 г. Пусть

g0 = 0.9876 -

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

= 0.97535376.

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

g1 = 0.5353.

Дальнейшая генерация аналогична:

= 0.28654609 Þ g2 = 0.6546, и так далее.

Этот пример демонстрирует основные особенности генераторов псевдослучайных чисел:

· использование предыдущих членов последовательности для получения следующих;

· получение очередного числа как части мантиссы некоторого промежуточного результата;

· существование конечного периода последовательности; в показанном примере последовательность повторится полностью после появления числа, совпадающего с одним из предыдущих (поскольку {gi+1=f(gi), gi+2=f(gi+1), ¼}, то совпадение gk = gi приведёт к тому, что gk+1=f(gk) =f(gi), и так далее).

Алгоритм генератора Mersenne Twister

Принцип работы генератора псевдослучайных чисел Mersenne Twister [11],[14], который мы в дальнейшем будем использовать, похож на показанный выше. Этот алгоритм относится к числу генераторов, основанных на линейных рекуррентных соотношениях, связывающих следующие элементы случайной последовательности {xi} с предыдущими.

Элементы последовательности xi в алгоритме Mersenne Twister рассматриваются как w-компонентные векторы из чисел 0 и 1 (в дальнейшем - векторы над полем F2), представляющие собой побитовое представление целых чисел w-битной точности. Ниже w = 32, поскольку именно это значение соответствует одинарной точности вычислений на графических процессорах.

Рекуррентное соотношение для генератора Mersenne Twister имеет вид

,

где - соединение r первых битов вектора xk с (w-r) последними битами вектора xk+1; r - параметр в диапазоне от 1 до w-1; - произвольная двоичная матрица размерности (w´w) над полем F2; «·» - операция скалярного умножения вектора x = справа на матрицу , при котором нули и единицы складываются по модулю 2 (операция XOR).



Для того, чтобы в умножение на матрицу могло быть представлено простой серией побитовых операций над числом x, эта матрица выбирается в виде

,

где a = [aw-1, aw-1, ¼, a0] – вектор над полем F2, представляющий некоторое целое число с побитовым представлением aw-1, aw-1, ¼, a0. Тогда умножение реализуется следующими побитовыми операциями:

Здесь - операция побитового сдвига числа x вправо на n битов, Å - сложение по модулю 2 (побитовая операция XOR). Для улучшения свойств случайного распределения, полученное число y умножается (операцией «·») на «закаливающую» (англ. tempering) матрицу Т, такую, что это умножение представляется следующей последовательностью побитовых операций:

z = y Å (z >> u);

z = z Å (z << s) AND b;

z = z Å (z << t) AND c;

z = z Å (z >> l);

Здесь u, s, t, l, b и c – параметры генератора, представляющие собой 32-битные векторы над полем F2, соответствующие некоторым целым числам w-битной точности. В результате всех операций, очередной элемент псевдослучайной последовательности xk (kn) оказывается функцией трёх предыдущих элементов:



.

Значения m и n, вместе с другими константами, входящими в формулы -, являются параметрами генератора. Первые n членов последовательности {x0, x1, ¼, xn-1} должны быть заданы как инициализирующая последовательность (англ. seeds).

Для перехода от случайной последовательности целых чисел {xi} к последовательности вещественных чисел g Î [0; 1] достаточно разделить все числа xi на 2w. Если w = 32, то

.

Период генератора и значения параметров алгоритма

Согласно работе [11], период генератора Mersenne Twister, - количество случайных чисел, генерируемых до зацикливания последовательности, - при оптимальных сочетаниях параметров дается формулой

T = 2nw-r - 1,

где n – длина инициализирующей последовательности {x0, x1, ¼, xn-1}, w и r – параметры алгоритма, рассмотренные выше. Для получения такого периода и максимального качества случайной последовательности, остальные параметры генератора (a, b, c, u, s, t, l) должны быть согласованы со значениями n, w и r [11].

В работе [11] были исследованы различные наборы параметров, в качестве лучшего из них, по качеству равномерного распределения, был принят набор n = 624, m = 397, r = 31, a = h9908B0DF, b = h9D2C5680, c = hEFC6000, u = 11, s = 7, t = 15, l = 18 [11]. Этим значениям соответствует период

T = 219937 - 1 » 106002 чисел,

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


Дата добавления: 2015-09-13; просмотров: 7; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты