Библиотека программиста

Все, что необходимо начинающему и опытному программисту

В свое время крупнейший математик и теоретик программирования Алан Тьюринг, отчаявшись найти чисто математическое решение проблемы, предложил использовать для генерации случайных чисел природные процессы, которые имеют истинно случайный характер. Один из таких процессов — тепловой шум, который приводит к небольшим флуктуациям тока в любом проводнике. На практике применяется резистор или специальный диод, спонтанные колебания тока в котором усиливаются и оцифровываются. Но такой довольно сложный генератор применяется лишь в специальной аппаратуре — городить его в составе микро-ЭВМ, конечно, нецелесообразно.

Поэтому в компьютерах распространен следующий прием. Есть математические методы, которые позволяют получить так называемую псевдослучайную последовательность чисел. Если начинать счет по такому алгоритму каждый раз с одного и того же числа, то полученная последовательность чисел будет детерминированной — одной и той же во всех случаях, но сами числа окажутся случайными, т. е. равномерно распределенными по вероятности в заданном диапазоне значений. Этой определенностью также широко пользуются — например, сигналы со спутника системы навигации GPS имеют именно такой псевдослучайный характер и для "постороннего" выглядят, как случайный шум. При этом каждый приемник "знает", с какого момента следует начинать отсчет, в результате чего псевдослучайные последовательности у приемника и источника совпадут, и сигнал легко расшифровывается.

Отсюда и метод — для генерации истинно случайных чисел достаточно произвольно выбрать число, с которого начинается отсчет псевдослучайной последовательности. Такое начальное число можно сгенерировать различными способами. Скажем, в различных системах программирования часто встречается инициализация по системному таймеру, из которого берется число, например, миллисекунд в произвольный момент времени. В AVR семейства Mega с асинхронно работающим таймером для отсчета истинно случайных чисел можно использовать его счетный регистр, если запустить его от независимого источника (например, от ЯС-цепочки, и чем более нестабильны ее параметры, тем лучше). Но мы вопрос инициализации генератора случайных чисел оставим за кадром, а сейчас сосредоточимся на собственно алгоритме генерации псевдослучайной последовательности.

Самый простой и широко распространенный алгоритм носит название линейно-конгруэнтного метода Лехмера, и сводится к формуле:
Х„+\ = (аХп + с) mod т.

Здесь Х„+\ — следующее псевдослучайное число последовательности, а ис — константы, называемые множителем и приращением соответственно; mod — операция нахождения остатка от деления на число ,т, которое называется модулем. От выбора модуля зависит длина последовательности, после которой она начинает повторяться. Для наших целей удобно (и достаточно) выбрать модуль, равный 256 — размеру одного байта. Тогда операция mod будет выполняться автоматически в процессе арифметических операций — в самом деле, для результата, меньшего величины 256, его значение уже само по себе будет остатком от его деления на 256, а большее значение автоматически усекается на величину 256 (например, сумма 240 и 20 даст 260, от которого в регистре останется значение 4), если не учитывать перенос. Именно с этим явлением мы боролись в главе 6, когда разбирали переполнение регистра при сложении, а здесь оно нам может пригодиться.
Теория гласит, что выбор величины приращения с достаточно произволен (в том числе оно может быть равно и нулю, но Кнут [11] утверждает, что лучше, если с — нечетное число, например, равное единице). А множитель а в нашем случае, когда модуль представляет собой степень двойки более 4, должен, согласно тому же источнику [11], быть равным 3 или 5. Пусть а = 5, тогда весь алгоритм генерации сведется к выбору начального числа Nrandom (любым из указанных ранее методов, например, чтением регистра таймера в случайный момент времени) и подсчету следующих чисел (листинг 7.8).

mov temp,N_random /временно сохраняем значение N_random
lsr N_random /умножили на 2
Is г N_random /умножили на 4
add N_random,temp /умножили на 5
inc N_random /прибавили с = 1

Естественно, для получения достаточно длинной последовательности такой алгоритм следует выполнять в цикле. "Искусственное" умножение на 5 такой последовательностью операций в МК семейства Mega можно заменить, разумеется, командой mul, причем старший байт результата (он окажется в регистре rl) при этом следует игнорировать (листинг 7.9).
Листинг 7.9
ldi. temp,5
mul N_random,temp ;умножили на 5
mov N_random,rO
inc N_random /прибавили с = 1

Операции с числами в формате BCD
Это важная группа операций — ведь значительная часть устройств на основе МК предназначена для демонстрации чисел в том или ином виде. Это, естественно, можно делать только в десятичном формате, в то время как внутреннее представление чисел в регистрах — двоичное.
Напомним, что числа в двоично-десятичном формате (binary-coded decimal, BCD) могут существовать в двух видах— упакованном и неупакованном. Неупакованный формат попросту означает, что мы тратим на каждую десятичную цифру не тетраду, как необходимо, а целый байт. Зато при этом не возникает разночтений: $05 = 05ю и никаких проблем.

Однако ясно, что это крайне неэкономично— байтов требуется в два раза больше, а старший полубайт при этом все равно всегда ноль. Потому BCD-числа при хранении в регистрах всегда упаковывают, занимая и старший разряд второй десятичной цифрой: скажем, число 59 при этом и запишется, как просто 59. Однако это не шестнадцатеричные $59! 59 в шестнадцатеричной форме запишется как $ЗВ, а у нас 59 процессор прочтет как 5 х 16 + 9 = 89, что вообще к нашим значениям не имеет отношения. Поэтому перед проведением операций с упакованными BCD-числами их распаковывают, перемещая старший разряд в отдельный байт и заменяя в обоих байтах старшие полубайты нулями.
В некоторых микропроцессорных системах (в их число входит интеловское семейство х5\ и, кстати, х$6) имеется специальная инструкция для т. н. двоично-десятичной коррекции, которая позволяет получить верный результат при сложении двоично-десятичных чисел в упакованном формате. Но в системе команд AVR такой инструкции нет, и она все равно не очень-то полезна, т. к. математические операции в любом случае удобнее производить в "родной" двоичной форме, а для представления на дисплее числа так или иначе приходится распаковывать. В ПК этим незаметно для пользователя занимаются процедуры на языках высокого уровня (да так успешно, что приходится скорее озадачиваться обратной проблемой— представлением десятичных чисел в двоичной/шестнадцатеричной форме), ну а на уровне ассемблера десятичные преобразования приходится делать, что называется, ручками.

<< Назад         В начало         Далее >>

Библиотека программиста. 2009.
Администратор: admin@programmer-lib.ru