Курсовая работа: Генерирование псевдослучайных чисел на примере создания игры Сапер

Третий класс АГСЧ– это "фундаментальный" класс. Наиболее яркий представитель "фундаментальных" АГСЧ - оптический квантовый генератор случайных чисел". Также существует устройство, в котором фундаментальные физические принципы, наносекундная синхронизация и самая современная электроника подчинены решению самой утилитарной задачи - получению случайных чисел, обновляющихся 100 тыс. раз в секунду.

Четвертый класс АГСЧ можно условно назвать "паразитным персонально-компьютерным". К их свойствам относятся прежде всего тепловые шумы и флуктуации в подсистеме аналогового ввода/вывода звукового адаптера.

В отдельный класс "курьезных" АГСЧ можно выделить специализированных роботов, методично бросающих... обычные игральные кости и оснащенных системой технического зрения для считывания выпавших очков.

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

¾ Слишком короткий период/периоды

¾ Последовательные значения не являются независимыми

¾ Некоторые биты «менее случайны», чем другие

¾ Неравномерное одномерное распределение

¾ Обратимость

Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, алгоритм Блюма, Блюма и Шуба, Вихрь Мерсенна.

Линейный конгруэнтный метод

Данный алгоритм был предложен Д. Х. Лемером в 1948 году. Применяется в простых случаях и не обладает криптографической стойкостью. Используется в качестве стандартного генератора многими компиляторами.

Этот алгоритм заключается в итеративном применении формулы (1):

(1)

где a > 0, c > 0, M > 0 — некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X₀ и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности X_j определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда:

1. НОД (c, m) = 1 (то есть c и m взаимно просты);

2. a - 1 кратно p для всех простых p — делителей m;

3. a - 1 кратно 4, если m кратно 4.

При реализации выгодно выбирать m = 2^e , где e — число бит в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.

Формула (2) для вычисления n -й члена последовательности, зная только 0-й

(2)

Метод Фибоначчи с запаздываниями.

Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делает невозможным их использование в статистических алгоритмах, требующих высокого разрешения.[2]

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел.

Наибольшую популярность фибоначчиевы датчики получили в связи с тем, что скорость выполнения арифметических операций с вещественными числами сравнялась со скоростью целочисленной арифметики, а фибоначчиевы датчики естественно реализуются в вещественной арифметике.

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле (3):

X(k) = \left\{ \begin{matrix} X(k-a)-X(k-b), & \mbox{if } X(k-a)\geq X(k-b); \\ X(k-a)-X(k-b)+1, & \mbox{if } X(k-a) < X(k-b);\end{matrix}\right. (3)

где X(k) — вещественные числа из диапазона [0, 1),

a, b — целые положительные числа, называемые лагами.