Ревич, Ю.В. Программирование микроконтроллеров AVR: от Arduino к ассемблеру

Глава 8. Арифметические операции и операции в двоично-десятичном формате 209 ков радиоволн, даже если их мощность многократно превышает мощность полезно­ го сигнала. Отсюда и метод - для генерации истинно случайных чисел достаточно произволь­ но выбрать число, с которого начинается отсчет псевдослучайной последователь­ ности. Такое начальное число можно сгенерировать различными способами. В раз­ личных системах программирования часто встречается инициализация по систем­ ному таймеру, из которого берется число, например, миллисекунд в произвольный момент времени. В АVR семейства Mega с асинхронно работающим таймером для отсчета истинно случайных чисел можно использовать его счетный регистр, если запустить его от независимого источника (например, от RС-цепочки, и чем более нестабильны ее параметры, тем лучше). Но мы вопрос инициализации генератора случайных чисел оставим за кадром, а сейчас сосредоточимся на собственно алгоритме генерации псевдослучайной последовательности. Самый простой и широко распространенный алгоритм носит название линейно­ конгруэнтного метода Лехмера [ 1 4] и сводится к формуле: Хп+ \ = (аХп + с) mod т. Здесь Хп+ 1 - следующее псевдослучайное число последовательности, а и с - кон­ станты, называемые множителем и приращением, соответственно, mod - опера­ ция нахождения остатка от деления на число т, которое называется модулем. Or выбора модуля зависит длина последовательности, после которой она начинает по­ вторяться . Для наших целей удобно (и достаточно) выбрать модуль, равный 256 - размеру одного байта. Тогда операция mod будет выполняться автоматически в процессе арифметических операций - в самом деле, для результата, меньшего величины 256, его значение уже само по себе будет остатком от его деления на 256, а большее значение автоматически усекается на величину 256, если не учитывать перенос (например, сумма 240 и 20 даст 260, от которого в регистре останется зна­ чение 4). Именно с этим явлением мы боролись в главе 7, когда рассматривали пе­ реполнение регистра при сложении, а здесь оно нам может пригодиться . Теория гласит, что выбор величины приращения с достаточно произволен (в том числе оно может быть равно и нулю, но Кнут [ 1 4] утверждает, что лучше, если с ­ нечетное ·число, например, равное единице) . А множитель а в нашем случае, когда модуль представляет собой степень двойки более 4, должен, согласно тому же ис­ точнику, быть равным 3 или 5 . Пусть а = 5, тогда весь алгоритм генерации сведется к выбору начального числа N_random (любым из указанных ранее методов - на­ пример, чтением регистра таймера в случайный момент времени) и подсчету сле­ дующих чисел (листинг 8 . 8) . mov temp, N_random ; временно сохраняем значение N_random lsr N_random ; умножили на 2 lsr N_random ; умножили на 4 add N_random, temp ; умножили на 5 inc N random ; прибавили с = 1