Лекции.Орг


Поиск:




Категории:

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

 

 

 

 


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




Наилучшие из известных сегодня методов имитации случайных чисел представляют собой частные случаи схемы, предложенные в 1948 году Д.Х.Лемером.

Суть метода: Выбираем четыре "магических числа":

– начальное значение,

– множитель,

– приращение,

– модуль,

Тогда искомая последовательность случайных чисел получается из соотношения:

(7.1)

т. е. каждое случайное число – это остаток, при делении (axi+c) на m (операция Mod - "определение остатка", термин взят от слова "modulo" – в переводе "остаток").

Последовательность, полученная из соотношения (7.1) называется линейной конгруэнтной последовательностью.

Пример: x0 = a = c = 7, m = 10.

Тогда последовательность имеет вид: 7, 6, 9, 0, 7, 6, 9, 0,…

Как видно, при выбранных значениях "магических чисел" последовательность почти сразу "зациклилась", длина периода = 4.

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

Метод получения случайных чисел при c=0 называется "мультипликативный конгруэнтный метод", при - "смешанный конгруэнтный метод". При c=0, выработка последовательностей происходит быстрее, но при этом уменьшается длина периода последовательностей.

Первоначально в методе Лемера было принято c=0. Идея получения более длинных последовательностей за счет принадлежит Томпсону и независимо Ротенбергу.

Выбор модуля m. Для получения длинных последовательностей и для увеличения скорости вычисления рекомендуется m выбирать равным размеру машинного слова. Для 32х разрядного машинного слова m = 231=2147483648, (левый нулевой бит слова отведен под знак числа).

При этом в 32х разрядном машинном слове, максимальное целое число, размещающее в машинном слове, равно

Тогда

Значение множителя также влияет на длину периода последовательностей. По этому вопросу также проведено много исследований.

Линейные конгруэнтные последовательности – не единственный из предложенных источников случайных чисел. Его можно обобщить, превратив его, например, в квадратичный конгруэнтный метод

Известен квадратичный метод, предложенный Р. Ковэю:

Известен метод получения случайных чисел, где реализуется последовательность Фибоначчи:

Известен также метод получения случайных чисел, предложенный Грином:

где k- большое число.

Имеются еще, так называемые, аддитивные методы, где не требуются операции умножения и деления, и другие методы.

 





Поделиться с друзьями:


Дата добавления: 2018-11-11; Мы поможем в написании ваших работ!; просмотров: 394 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Два самых важных дня в твоей жизни: день, когда ты появился на свет, и день, когда понял, зачем. © Марк Твен
==> читать все изречения...

2253 - | 2077 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.007 с.