Глава 5

5.Программирование вычисления функций

5.1.Возведение в квадрат и извлечение квадратного корня

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

65536*(Х{1)*Х(1)) + 256*(2*Х(1)*Х(0)) +Х(0)*Х(0).

В отличие от перемножения двухбайтовых чисел здесь произведение старшего и младшего байтов нужно вычислять только один раз, поэтому возведение в квадрат выполняется быстрее. Пусть исходное число записано в регистрах Rl, RO. Приведем программу, записывающую квадрат этого числа в регистры R3, R2, R1, R0:

MOV A, R1

MOV В, А

MUL АВ ; квадрат ст. байта

MOV R2, А

MOV R3, В ; во 2-й байт квадрата

MOV A, R0 ; в 3-й байт квадрата

MOV В, А

MUL АВ ; квадрат мл . байта

XCH R0, A ; в 0-й байт квадрата

ХСН А, В

ХСН Rl, A ; в 1-й байт квадрата

MUL AB ; произведение ст. байта на мл. байт

RLC A

ХСН А, В

RLC A ; произведение удвоено

JNC sqrl ; переход по отсутствию переноса

INC R3 ; коррекция 3-го байта квадрата

sqrl: ХСН А, В

ADD A, Rl

MOV Rl, A ; в 1-й байт квадрата

MOV A, R2

ADDC А, В

JNC sqr2 ; переход по отсутствию переноса

INC R3 ; коррекция 3-го байта квадрата

sqr2: MOV R2, A ; во 2-й байт квадрата

За счет записи младших байтов результата в те же регистры, где находилось исходное число, экономятся ресурсы ОЗУ и ПЗУ.

Вычисление обратной функции, то есть извлечение квадратного корня, немного труднее. Обратные функции, как правило, вычисляются труднее, а разрешение некоторых из этих трудностей ведет к новым знаниям. Помня о мнимых числах, будем рассматривать извлечение корня только из положительного числа. Существует несколько алгоритмов непосредст­венного вычисления квадратного корня. Начнем с метода, основанного на представлении квадрата целого числа N суммой нечетных чисел от 1 до 2*N - 1. Нетрудно убедиться, что разность квадратов соседних чисел всегда нечетна:

N*N - (N - 1)*(N - 1) = 2*N - 1.

Последовательно вычитая из числа, корень которого требуется определить, нечетные числа 1, 3, 5 и так далее, нужно прекратить вычитание тогда, когда разность станет меньше нуля. Теперь по последнему вычитаемому можно вычислить целую часть значения корня. Пусть в А находится число от 0 до 255. Приведем программу, записывающую целую часть корня от этого числа в накопитель:

CLR С ; подготовка к вычитанию

MOV В, #FFh ; заготовка для вычитаемого

sqrt: INC В ; увеличение вычитаемого (четное)

INC В ; увеличение вычитаемого (нечетное)

SUBB А, В ; вычисление разности

JNC sqrt ; повторение по неотрицательной разности

MOV А, В ; вычитаемое

DEC A ; четное число

RR А ; корень

Недостатком этой программы является существенная зависимость времени вычисления от значения аргумента. Кроме того, вычисленное значение корня всегда меньше истинного, то есть содержит систематическую погрешность.

Рассмотрим пример со значительно лучшими временными характери­стиками. В отличие от рассмотренной программы займемся вычислением значения корня с округлением до ближайшего целого. Хорошо известное мнемоническое правило ускоренного вычисления квадрата целого деся­тичного числа, оканчивающегося на 5, можно переписать в измененном виде:

(N + 0,5)*(N + 0,5) = N*(N + 1) + 0,25.

Это выражение позволяет легко получить ряд граничных значений аргу­мента, по которым можно определить округленное до целого значение корня простыми сравнениями:

0*1=0, 1*2=2, 2*3=6, 3*4=12, 4*5=20, ...

Если аргумент находится в интервале от 0 до 2 (исключая левую границу и включая правую), то округленное значение корня равно 1, если от 2 до 6, то 2, если от 6 до 12, то 3 и так далее. Притом поиск подходящего интервала можно произвести наискорейшим образом, сравнив аргумент сначала со значением 72. Если он больше, то в 3-ий разряд корня нужно записать единицу, если не больше, то 0. Затем надо сравнить аргумент со значением 156 в первом случае или 20 во втором, что позволяет определить значение второго разряда корня. После третьего и четвертого сравнений определяются соответственно значения первого и нулевого разрядов. Этот метод нахождения подходящего интервала называется поиском по двоичному дереву и широко используется в программировании. Полу­чаемый после завершения поиска номер интервала находится в пределах от 0 до 15, поэтому по завершении поиска для получения числового значения корня к полученному номеру добавляется 1. По сравнению с предыдущим этот алгоритм более чем на порядок уменьшает среднюю погрешность вычислений, хотя максимальная погрешность уменьшается только вдвое.

В приводимой программе аргумент функции записывается в накопи­тель, а значение корня получается в регистре В:

MOV B, #0 ; заготовка для корня

JZ lt1 ; переход по нулевому корню

CJNE A, #8*9, lt8 ; порог 72

JC it8 ; переход по корню меньше 8,5

ORL B, #8 ; запись 1 в 3-ий разряд

CJNE A, #12*13, ltl2 ; порог 156

JC ltl2 ; переход по корню меньше 12,5

ORL B, #4 ; запись 1 во 2-ой разряд

CJNE A, #14*15, ltl4 ; порог 210

JC ltl4 ; переход по корню меньше 14,5

ORL B, #2 ; запись 1 в 1-ый разряд

CJNE A, #15*16, ltl5 ; порог 240

JC ltl5 ; переход по корню меньше 15,5

SJMP gel 5 ; переход по корню больше или равно 15,5

It8: CJNE A, #4*5, lt4 ; порог 20

JC lt4 ; переход по корню меньше 4,5

ORL B, #4 ; запись 1 во 2-ой разряд

CJNE A, #6*7, lt6 ; порог 42

JC lt6 ; переход по корню меньше 6,5

ORL B, #2 ; запись 1 в 1-ый разряд

CJNE A, #7*8, ltl5 ; порог 56

JC ltl5 ; переход по корню меньше 7,5

SJMP ge15 ; переход по корню больше или равно 7, 5

ltl2: CJNE A, #10*11, ltl0 ; порог 110

JC ltlO ; переход по корню меньше 10,5

ORL B, #2 ; запись 1 в 1-ый разряд

CJNE A, #11*12, ltl5 ; порог 132

JC ltl5 ; переход по корню меньше 11,5

SJMP ge15 ; переход по корню больше или равно 11,5

ltl4: CJNE A, #13*14, ltl5 ; порог 182

JC ltl5 ; переход по корню меньше 13,5

SJMP ge15 ; на запись 1 в 0-ой разряд

lt4: CJNE A, #2*3, It2 ; порог 6

JC lt2 ; переход по корню меньше 2,5

ORL B, #2 ; запись 1 в 1-ый разряд

CJNE A, #3*4, ltl5 ; порог 12

JC ltl5 ; переход по корню меньше 3,5

SJMP ge15 ; переход по корню больше или равно 3, 5

lt6: CJNE A, #5*6, ltl5 ; порог 30

JC ltl5 ; переход по корню меньше 5,5

SJMP ge15 ; переход по корню больше или равно 5, 5

ltlO: CJNE A, #9*10, ltl5 ; порог 90

JC lt15 ; переход по корню меньше 9,5

SJMP ge15 ; переход по корню больше или равно 9, 5

lt2: CJNE A, #1*2, ltl5 ; порог 2

JC ltl5 ; переход по корню меньше 1,5

ge15: ORL B, #1 ; запись 1 в 0-ой разряд

ltl5: INC В ; коррекция значения корня

ltl: NOP ; для записи метки

В процессе работы программы содержимое накопителя не изменяется. Обратите внимание на то, как записаны значения порогов в командах сравнения. Выражения с операцией умножения перекладывают вычисле­ние пороговых значений на транслятор. Конечно, эта программа занимает гораздо больше места в ПЗУ, нежели предыдущая, но зато в большинстве случаев она и работает быстрее. Из 15 сравнений выполняется только 4, то есть в среднем выполняется только четверть всех команд программы. Этот пример еще раз демонстрирует, что зачастую экономия времени вычисления может быть достигнута за счет затрат объема ПЗУ.

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