Генерация последовательности случайных чисел
Знание некоторых принципов нередко возмещает незнание некоторых фактов.
Гельвецкий
Важный класс вычислительных алгоритмов, востребованных на практике, – алгоритмы генерации последовательности случайных величин. По определению, последовательностью случайных чисел является последовательно формируемый массив значений, в котором каждый очередной элемент получен вне всякой связи с другими его элементами и появление этого элемента возможно с вероятностью, подчиненной некоторому закону распределения. К примеру, если появление любого числа в этой последовательности равновероятно, то говорят о равномерном законе распределения случайных чисел.
На практике в большинстве случаев применяются программные методы получения случайных чисел. На самом дел'е случайные последовательности, получаемые по некоторому алгоритму, являются псевдослучайными. Это происходит из-за того, что связь между значениями в последовательности, получаемой программным путем, обычно все-таки существует. Данное обстоятельство приводит к тому, что на каком-то этапе генерируемая последовательность чисел начинает повторяться – "входит в период".
Рассмотрим несколько наиболее известных и пригодных для практического использования программных методов генерации псевдослучайных величин (все же, понимая смысл выражения, будем по привычке и для удобства называть их случайными).
Конгруэнтный метод генерации последовательности случайных чисел
Конгруэнтный метод генерации последовательности случайных чисел получил широкое распространение. Он описан во многих источниках, но конкретных рекомендаций по его использованию на платформе Intel автор не встретил. Попытаемся устранить этот недостаток.
В основе этого метода генерации последовательности случайных чисел лежит понятие конгруэнтности. По определению, два числа А и В конгруэнтны (сравнимы) по модулю М в случае, если существует число К, при котором А-В=КМ, то есть если разность А-В делится на М, и числа А и В дают одинаковые остатки от деления на М. Например, числа 85 и 5 конгруэнтны по модулю 10, так как при делении на 10 дают остаток 5 (при К=1). В соответствии с этим методом каждое число в этой последовательности получается исходя из следующего соотношения:
Хn+1=(аХn+с) mod m, где n > 0. (1)
При задании начального значения Хо, констант а и с данное соотношение однозначно определяет последовательность целых чисел X,, составленную из остатков от деления на m предыдущих членов последовательности, в соответствии с соотношением (1). Величина этих чисел не будет превышать значение т. Если каждое число этой последовательности разделить на т, то получится последовательность случайных чисел из интервала 0.1.1'. Но не спешите подставлять в это соотношение какие-либо значения.
Основная трудность при использовании этого метода – подбор компонентов формулы. В зависимости от значения с различают два вида конгруэнтного метода – мультипликативный (с=0) и смешанный (с не равно 0).
Для простоты изложения будем генерировать небольшие по величине случайные числа. Это дает возможность легко отслеживать особенности работы рассматриваемых алгоритмов с использованием стандартной возможности перенаправления ввода-вывода. Для этого необходимо, чтобы текст программы содержал строки:
movdl.ah mov ah.02 int 21h
Запуск программы производиться командной строкой вида:
prog.exe > p.txt
При этом создается файл p.txt, в который и выводятся результаты работы программы. Если не использовать этой возможности, то вывод будет производиться на экран, что не очень удобно для последующего анализа получающейся последовательности случайных чисел. Более подробно о возможностях работы с файлами и экраном читайте материал в главах 5 и 7, посвященных работе с файлами и консолью из программ на языке ассемблера.
Большинство представленных ниже программ функционируют в бесконечном цикле, с тем, чтобы можно было изучать периодичность последовательности, создаваемой по тому или иному методу генерации случайных чисел. Поэтому для окончания работы программы ее необходимо завершить принудительно (при работе в Windows для этого можно просто закрыть окно DOS). В результате работы программы будет создан файл p.txt, который можно открыть в любом редакторе, допускающем просмотр файлов в шестнадцатеричном виде (например, встроенном редакторе файлового менеджера Windows Commander).
Для увеличения диапазона необходимо внести соответствующие, не принципиальные с точки зрения алгоритма, изменения в тексты программ.