17.Мультипликативный конгруэнтный метод получения равномерно распределенных псевдослучайных чисел
Конгруэнтный метод представляет собой арифметическую процедуру для генерирования конечной последовательности равномерно распределенных чисел. С использованием нескольких рекуррентных формул было построено множество конгруэтнных алгоритмов. В основе каждого из них лежит фундаментальное понятие конгруэнтности (два целых числа A и B конгруэнтны(сравнимы) по модулю m(где m-целое число) тогда и только тогда, когда существует такое целое число k, что A-B=km, т.е если разность A-B делится на m и если числа А и В дают одинаковые остатки при делении на абсолютную величину числа m. Это определение записывается как A=B(mod m) и читается «A конгруэнтно В по модулю m» ) Основная формула мультипликативного конгруэнтного метода имеет вид : Хi+1=aX1 (mod m), где a и m – неотрицательные целые числа. Согласно этому выражению, мы должны взять последнее случайное число Хi , умножить его на постоянный коэффициент а и взять модуль полученного числа по m. Поэтому для генерирования последовательности чисел Хi нам необходимы начальные данные Х0 , множитель а и модуль m. Любой генератор псевдослучайных чисел может дать лишь конечное множество целых случайных чисел, после которого последовательность начинает повторяться. Период, или длина последовательности, Р зависит от вычислительной машины и от выбранного модуля, а статистические свойства полученной последовательности зависят от выбора начального значения и множителя. Выбрать а, Х0 и m следует так, чтобы обеспечить максимальный период и минимальную корреляцию между генерируемыми числами.
19. Программный датчик randu. Общая характеристика, принцип работы, особенности
Этот датчик специально предназначен для системы IBM и образует 229 значений перед началом повторений, т.е. длина цикла равна 229 (при 32-х разрядном машинном слове). Алгоритм датчика реализует метод остатка степеней (рис. 8.1).
Назначение датчика RANDU:
Вычисление равномерно распределенных случайных действительных чисел YF в интервале [0,1] и случайных целых чисел IY в интервале [0,231]. В качестве входа служит целое случайное число IX, на выходе образуется новое целое число IY и вещественное YF.
Обращение к датчику:
RANDU (IX,IY,YF).
Описание параметров:
IX – при первом обращении – нечетное целое число с числом цифр
После первого обращения IX=IY, где IY – целое число, вычисленное при предыдущем обращении.
IY – полученное в результате целое случайное число, требуемое при последующих обращениях. IY находится в интервале [0, 231].
YF– полученное в результате равномерно распределенное действительное число в интервале [0,1], представленное в форме с плавающей запятой.
Рис. 8.1. Алгоритм датчика RANDU
Используя датчик RANDU, построим алгоритм вычисления последовательности равномерно распределенных случайных чисел и ее печать (рис. 8.2).
Рис. 8.2.
Алгоритм вычисления последовательности равномерно распределенных случайных чисел.
Исходные данные:
N - длина последовательности (количество испытаний).
IX - начальное значение, нечетное целое число с числом цифр <9.
Например: IX = 1234567.
Различные начальные значения параметра IX позволяют формировать различные последовательности равномерно распределенных псевдослучайных чисел.
Для генерирования равномерно распределенных случайных чисел на отрезке [0,1] используется отделение дробной части от сложного арифметического выражения, содержащего предшествующее число.
Vi+1 =FRAC(k Vi)
FRAC – оператор выделения дробной части,
Vi - предшествующее случайное число,
Vi+1 - последующее случайное число,
k-8t = 3,
t - нечетное целое число.
Задание различных начальных значений V0 позволяет формировать различные последовательности случайных чисел.
Количество случайных чисел в одном периоде от нескольких тысяч до сотен тысяч.
Для перевода равномерно распределенных случайных чисел из отрезка [0,1] в отрезок [а,b] можно использовать:
xi+1= a + (b-a)Vi+1.