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

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

Как видите, число задействованных регистров то же самое, но процедура получилась значительно короче. Недостаток этого способа, кроме большей длительности выполнения — здесь мы напрямую не получаем остатка. Его все же можно получить, если прибавить к тому отрицательному числу, что осталось в регистрах countxx, значение делителя (как бы вернуться на одну итерацию назад), либо если оборвать цикл за одну итерацию до того, как выполнится условие переноса в минус (каждый раз сравнивая значение делимого с делителем — как только первое станет меньше второго, цикл можно обрывать). Другой недостаток— здесь приходится выделять специальные регистры под результат, а делимое при этом все равно окажется испорченным.

Но зато этот алгоритм легко масштабируется: для того чтобы вместо деления 32-битового числа на 8-битовое получить деление 32-битового на число с большей разрядности, достаточно в командах sbc вместо нуля подставить соответствующий разряд делителя. При меньшей разрядности исходных чисел и результата из процедуры просто удаляют строки с участием ненужных старших регистров.

Многие подобные задачи на деление удается решить еще более простым и менее громоздким методом, если заранее подгадать так, чтобы делитель оказался кратным степени двойки. Тогда все деление сводится, как мы знаем, к сдвигу разрядов вправо столько раз, какова степень двойки. Для примера предположим, что мы некую величину измерили 64 раза, и хотим узнать среднее. Пусть сумма укладывается в два байта, тогда вся процедура деления будет такой, как в листинге 7.6.

/деление на 64
clr count_data /счетчик до б
div64L:
Isг dataH /сдвинули старший вправо ror dataL /сдвинули младший с переносом inc
count_data cpi count_data, б brne div64L
He правда ли, гораздо изящнее и понятнее, чем деление "в лоб"?

Операции с дробными числами
Усвоив такой прием, попробуем на радостях решить задачку, которая на первый взгляд требует, по крайней мере, знания высшей алгебры — умножить некое число на дробный коэффициент (вещественное число с "плавающей запятой"). Теоретически для этого требуется представить исходные числа в виде "мантисса-порядок", сложить порядки и перемножить мантиссы. Нам же неохота возиться с этим представлением, т. к. мы не проектируем универсальный компьютер, и в подавляющем большинстве реальных задач все конечные результаты у нас представляют собой целые числа (запятая в электронных схемах с индикацией результатов устанавливается на нужном месте принудительно). На самом деле эта задача решается очень просто, если ее свести к последовательному умножению и делению целых чисел, представив реальное число в виде целой дроби с оговоренной точностью. Например, число 0,48576 можно представить, как 48576/100000. И если нам требуется на такой коэффициент умножить, к примеру, результат какого-то измерения, равный 976, то можно действовать, не выходя за рамки диапазона целых чисел: сначала умножить 976 на 48 576 (получится заведомо целое число 47 410 176), а потом поделить результат на L05, чисто механически перенеся запятую на пять разрядов. Получится 474,10176 или, если отбросить дробную часть, 474.
Большая точность нам и не требуется, т. к. исходное число 976 имело три десятичных разряда.

С числами в десятичном виде хорошо работать "руками", просто отсчитывая разряды. Нам же делить на сто тысяч в 8-разрядном МК крайне неудобно — представляете, насколько громоздкая процедура получится? Наше ноу-хау будет состоять в том, что мы для того, чтобы "вогнать" дробное число в целый диапазон, будем использовать не десятичную дробь, а двоичную — деление тогда сведется к вышеописанной механической процедуре сдвига, аналогичной переносу запятой в десятичном виде.
Итак,\гобы умножить 976 на коэффициент 0,48576, следует сначала последний "вручную" умножить, например, на 216 = 65 536, и таким образом получить числитель соответствующей двоичной дроби (у которой знаменатель равен 65 536)— он будет равен 31834,76736, или, с округлением до целого, 31 835. Такой точности хватит, если исходные числа не выходят, как у нас, за пределы трех-четырех десятичных разрядов. Теперь мы в контроллере должны умножить исходную величину 976 на константу 31 835 и полученное число 31 070 960 (оно оказывается 4-байтовым— $01DA1AF0) сдвинуть на 16 разрядов вправо (листинг 7.7).

/в ddHH:ddH:ddM:ddL число $01DA1AF0, ;его надо сдвинуть на 16 разрядов
clr cnt 1 divl6L: ;деление на 65536
Isг ddHH /сдвинули старший
гor ddH /сдвинули 3-й
гor ddM /сдвинули 2-й
ror ddL /сдвинули младший
inc cnt
cpi cnt,16
brne divl6L ;сдвинули-поделили на 2 в "l6

В результате, как. вы можете легко проверить, старшие байты обнулятся, а в. ddM:ddL окажется число 474— тот же самый результат. Но и это еще не все — такая процедура приведена скорее для иллюстрации общего принципа. Ее можно еще больше упростить, если обратить внимание на то, что сдвиг на восемь разрядов есть просто перенос значения одного байта в соседний (в старший, если сдвиг влево, и в младший — если вправо). Итого получится, что для сдвига на 16 разрядов вправо нам нужно всего-навсего отбросить два младших байта и взять из исходного числа два старших ddHH:ddH— это и будет результат. Проверьте— $01DA и есть 474. Никаких других действий вообще не требуется!

Если степень знаменателя дроби, как в данном случае, кратна 8, то действительно не нужно никакого деления, даже в виде сдвига, но чаще всего это не так. Однако и тут приведенный принцип может помочь: например, при делении на 215 (что может потребоваться, если, например, в нашем примере константа больше единицы) вместо пятнадцатикратного сдвига вправо результат можно сдвинуть на один разряд влево (фактически умножив число на два), а потом уже выделить из него старшие два байта. Итого процедура будет состоять из четырех операций и займет четыре такта. А в виде циклического сдвига на 15, как ранее, нам необходимо в каждом цикле выполнить четыре операции сдвига и одну увеличения счетчика, итого 15x5 = 75 простых одно-тактных операций, и еще 15 сравнений, из которых 14 займут два такта — всего 104 такта. А решение "в лоб" — на основе целочисленного деления — еще в несколько раз превышало бы и эту величину. Существенная разница, правда? Вот такая специальная арифметика в МК. Применение таких процедур на практике мы рассмотрим в главе 10.

Генератор случайных чисел
Настоящая генерация случайных чисел в МК требуется не так уж часто, потому что, например, достаточно зафиксировать значение счетного регистра таймера (при счете с переполнением) в произвольный момент времени, определяемый действиями пользователя (например, по нажатию им кнопки). Случайность здесь определяется тем, что таймер считает намного быстрее, чем человек успевает подготовиться к нажатию, и при всем желании попасть в определенное число невозможно.
Но если отказаться от участия человека с его непредсказуемостью и медленностью реакции, то проблема генерации случайных чисел становится довольно сложной. Ведь компьютер— система полностью детерминированная, в которой любое состояние однозначно выводится из предыдущих.

Заметки на полях
Над созданием хорошего компьютерного генератора случайных чисел бились лучшие математические умы, и эта проблема до сих пор однозначно не решена. Насколько она актуальна, можно судить по такому примеру: в конце 2007 г. израильские ученые из университета Хайфы обнаружили дефект в коде генератора случайных чисел (функция CryptGenRandom) в операционной системе Windows, из-за которого злоумышленник при желании может не только просчитать, какие шифровальные ключи будут создаваться системой, но и выяснить, какие из них генерировались ею в прошлом. Обратите внимание — дефект этот существовал со времен Windows 2000, т. е., по крайней мере, восемь лет до того, как его нашли.

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

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