Наилучшие из известных сегодня методов имитации случайных чисел представляют собой частные случаи схемы, предложенные в 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- большое число.
Имеются еще, так называемые, аддитивные методы, где не требуются операции умножения и деления, и другие методы.