![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод середины квадрата
Первым алгоритмический метод получения равномерно распределенных псевдослучайных чисел предложил Джон фон Нейман (один из основоположников кибернетики). Метод получил название " метод середины квадрата". Суть метода: предыдущее случайное число возводится в квадрат, а затем из результата извлекаются средние цифры. Например: и т.д. Как видно метод середины квадрата довольно хорошо должен " перемешивать" предыдущее число. Однако он имеет недостатки: 1. Если какой-нибудь член последовательности окажется равным нулю, то все последующие члены также будут нулями. 2. Последовательности имеют тенденцию " зацикливаться", т. е. в конце концов, образуют цикл, который повторяется бесконечное число раз. Свойство " зацикливаться" присуще всем последовательностям, построенных по рекуррентной формуле xi+1=f(x). Повторяющийся цикл называется периодом. Длина периода у различных последовательностей разная. Чем больше, тем лучше. Наилучшие из известных сегодня методов имитации случайных чисел представляют собой частные случаи схемы, предложенные в 1948 году Д.Х.Лемером. Суть метода: Выбираем четыре " магических числа":
Тогда искомая последовательность случайных чисел получается из соотношения:
т. е. каждое случайное число – это остаток, при делении (axi+c) на m (операция Mod - " определение остатка", термин взят от слова " modulo" – в переводе " остаток"). Последовательность, полученная из соотношения (*) называется линейной конгруэнтной последовательностью. Пример: x0 = a = c = 7, m = 10. Тогда последовательность имеет вид: 7, 6, 9, 0, 7, 6, 9, 0, … Как видно, при выбранных значениях " магических чисел" последовательность почти сразу " зациклилась", длина периода = 4. Из этого примера видно, что " магические числа" нельзя выбирать произвольно. Проведено много исследований и доказано теорем по вопросу " как правильно выбирать" " магические числа". Метод получения случайных чисел при c=0 называется " мультипликативный конгруэнтный метод", при Первоначально в методе Лемера было принято c=0. Идея получения более длинных последовательностей за счет Выбор модуля m. Для получения длинных последовательностей и для увеличения скорости вычисления рекомендуется m выбирать равным размеру машинного слова. Для 32х разрядного машинного слова m = 231=2147483648, (левый нулевой бит слова отведен под знак числа). При этом в 32х разрядном машинном слове, максимальное целое число, размещающее в машинном слове, равно Тогда Значение множителя также влияет на длину периода последовательностей. По этому вопросу также проведено много исследований. Линейные конгруэнтные последовательности – не единственный из предложенных источников случайных чисел. Его можно обобщить, превратив его, например, в квадратичный конгруэнтный метод Известен квадратичный метод, предложенный Р. Ковэю: Известен метод получения случайных чисел, где реализуется последовательность Фибоначчи: Известен также метод получения случайных чисел, предложенный Грином: где k- большое число. Имеются еще, так называемые, аддитивные методы, где не требуются операции умножения и деления, и другие методы.
Контрольные вопросы 1. В чем заключается принцип метода Монте-Карло? 2. Как раньше получали случайные числа без использования компьютеров? 2. Назовите методы генерации случайных чисел и их отличительные особенности. 4. Какие есть недостатки у метода середины квадратов? 5. Какие ограничения накладываются на генерацию случайных чисел на компьютере?
|