![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Конгруэнтные методы получения равномерно распределенных псевдослучайных чисел
Конгруэнтные методы генерирования случайных чисел получили наиболее широкое распространение для формирования на ЭВМ псевдослучайных последовательностей. Два целых числа a и b называются конгруэнтными (сравнимыми) по модулю m, где m – целое число, если разность (a − b) делится на m без остатка, а числа a и b дают одинаковые остатки от деления на m. Например, 2568 и 148 (по модулю 10), 1746 и 511 (по модулю 5), 6493 и 2221 (по модулю 2) и т.д. Конгруэнтные методы описываются в виде рекуррентного соотношения следующего вида: X i +1 = λ X i + ё (mod m) (i = 0, 1, 2,...), где X i, λ, ё, m – неотрицательные целые числа; X 0 – начальное значение псевдослучайной последовательности; λ – множитель; ё – аддитивная константа; m – модуль. Каждое новое значение X i +1 псевдослучайной последовательности представляет собой целочисленный остаток от деления на модуль m суммы произведения предыдущего значения X i на множитель λ и аддитивной константы ё. Последовательность псевдослучайных чисел в интервале (0; 1) формируется путем деления полученных целочисленных значений X i на модуль m: xi = X i / m (i = 1, 2,...). Описанный метод генерирования псевдослучайных чисел получил название смешанного конгруэнтного метода. В некоторых случаях используется более простой метод генерирования псевдослучайных чисел, представляющий собой частный случай смешанного метода, когда ё = 0, и получивший название мультипликативного конгруэнтного метода. В этом случае рекур- рентное соотношение имеет вид X i +1 = λ X i (mod m) (i = 0, 1, 2,...). На каждом шаге полученное случайное число (множимое) умножается на некоторое постоянное число (множитель) и затем делится на другое постоянное число (делитель). В качестве нового случайного числа принимается остаток от деления, который служит дробной частью случайного числа, равномерно распределённого в интервале (0; 1).
14. Метод середины квадрата. Общая характеристика, основные недостатки. Требования к функции
Одной из первых арифметических процедур, использованных для вычисления последовательностей равномерно распределенных псевдослучайных чисел, был метод серединных квадратов. В этом методе, предложенным фон Нейманом и Метрополисом в 1946 г., каждое новое число в последовательности получалось взятием средних m цифр из числа, полученного возведением в квадрат первоначального m-значного числа. Метод серединных квадратов состоит из следующих шагов: 1.взять произвольное четырехзначное число. 2.возвести его в квадрат и, если нужно, добавить слева нули до восьмизначного числа. 3. Взять четыре цифры из середины в качестве первого случайного числа. 4.возвести в квадрат четырехзначное число, полученное на щаге 3 (опять при необходимости добавляя слева нули до восьмизначного числа). 5.повторять шаги 3 и 4 до получения необходимого количества случайных чисел. Алгоритм получения последовательности случайных чисел методом серединных квадратов сводится к следующему: Пусть имеется 2 n -разрядное число, меньше 1:
Возведем его в квадрат:
а затем возьмем средние 2 n разрядов:
которые и будут очередным числом. Например:
Суть метода: предыдущее случайное число возводится в квадрат, а затем из результата извлекаются средние цифры. К сожалению этот метод трудно проанализировать, он работает сравнительно медленно и не дает статистически удовлетворительных результатов.так, например, корреляцию между первым числом и длиной неповторяющейся последовательности (называемой периодом) заранее оценить очень трудно. Весьма часто последовательность случайных числе может оказаться слишком короткой (или, что хуже, в ней может отсутствовать случайность). Прежняя популярность данного метода простотой описания и легкостью понимания. Можно указать еще такие недостатки: 1. Если какой-нибудь член последовательности окажется равным нулю, то все последующие члены также будут нулями, 2. Последовательности имеют тенденцию " зацикливаться", т. е. в конце концов, образуют цикл, который повторяется бесконечное число раз. Свойство " зацикливаться" присуще всем последовательностям, построенных по рекуррентной формуле xi+1=f(xi).
|