logo
М_М_К_3

1.3.2. Алгоритмы получения псевдослучайных чисел 5

Проведем случайный эксперимент, в результате которого наблюдаем или получаем случайное число. Используя это случайное число, по какой-либо заданной формуле преобразуем его в другое случайное число, затем повторяем эту итерацию, тогда в конечном счете получаем ряд случайных чисел. Таким образом, полученные случайные числа называются псевдослучайными числами. Отметим, что при использовании формул для получения случайных чисел через какое-то число испытаний начинается повторение случайных чисел, т.е. псевдослучайные числа периодичны, иначе говоря, запас псевдослучайных чисел ограничен. Вопрос состоит только в том, каков период псевдослучайных чисел? Это зависит от выбранного алгоритма выработки псевдослучайных чисел.

Существует достаточное количество способов получения псевдослучайных чисел (см. в работах [5, 13, 22]). Рассмотрим без доказательства несколько способов получения псевдослучайных чисел.

  1. Последовательность псевдослучайных чисел xi, i= 1, 2, ..., можно полу­чить с помощью способа Лемера, или как говорят иногда методом вычетов. Алгоритм этого способа со­стоит в следующем [70]:

  1. Первое случайное целое число r1 выбирается между числами 0 и P, где число Р выбирается заранее.

  2. Умножаем это случайное число на выбранный заранее постоянный множитель М.

  3. К полученному произведению прибавляем некоторое выбран­ное заранее целое число К.

  4. Результат первых трех шагов делим на Р и получившийся остаток выбираем в качестве следующего случайного числа. Формула представленного алгоритма имеет следующий вид: ri+1 = (M ri + К) mod P, i = 1, 2, ... Выбор различных значений М, К и Р дает различные периоды псевдослучайных последовательностей. Доказано, что лучше всего использовать целые числа. При К=0, а Р = 2 N наибольший период достигается при М=3+8*I или М = 5+8*I. В качестве начального числа r1 желательно выбрать нечетное число. При достаточно больших числах М полученный ряд производит впечатление случайного ряда.

  1. Для получения случайного числа можно использовать также другой алгоритм Лемера:

    1. Берем случайное число  и умножим его 102*k (0 =*102*k )

    2. Возводим в квадрат 0 2

    3. Берем последние 2*k от 0 2

    4. Умножим на постоянное любое число С, получаем новое число 1.

    5. Берем первые 2*k цифры от 1, тогда получим число 2.

    6. Берем первые 2*k от 0 2

    7. Умножим на постоянное любое число С, получаем новое число 3.

    8. Берем последние 2*k цифры от 3 , тогда получим число 4.

    9. Случайное число = (1+2)/(2*102*k).

  2. Для генерирования эталонных псевдослучайных чисел можно также воспользоваться методом середины квадратов (метод Неймана), суть которого заключается в следующем: пусть тогда , берем средние четыре цифры и составим , тогда Следовательно, и т.д., т.е. каждое последующее число образуется возведением предыдущего в квадрат и отбрасыванием цифр с обоих концов.

  3. Следующий класс генераторов случайных чисел предложен А.Зейманом и Дж.Марсалиа. Генераторы этого типа основаны на использовании последовательности Фибоначчи. Пример такой последовательности {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ….}. Рекурсивное описание последовательности Фибоначчи имеет вид , т.е. каждый последующий член равен сумме предыдущих. Если мы берем только последнюю цифру каждого числа в последовательности, то получим последовательность чисел {0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4 ….}. Если эта последовательность применяется для начального заполнения массива большой длины, то используя этот массив, можно создать генератор случайных чисел Фибоначчи с запаздыванием, где складываются не соседние, а удаленные числа.