Глава 5
5.1.Возведение в квадрат и извлечение квадратного корня
За изучением арифметики в школе приступают к началам алгебры, и в дополнение к четырем действиям арифметики ученики знакомятся с возведением в квадрат и извлечением квадратного корня. Поэтому естественно рассмотреть эти алгебраические операции в качестве примера вычисления простейших функций. Начнем с возведения в квадрат числа, занимающего два байта. Запишем формулу квадрата суммы:
В отличие от перемножения двухбайтовых чисел здесь произведение старшего и младшего байтов нужно вычислять только один раз, поэтому возведение в квадрат выполняется быстрее. Пусть исходное число записано в регистрах Rl, RO. Приведем программу, записывающую квадрат этого числа в регистры R3, R2, R1, R0:
MUL АВ ; квадрат ст. байта
MOV R3, В ; во 2-й байт квадрата
MOV A, R0 ; в 3-й байт квадрата
MUL АВ ; квадрат мл . байта
XCH R0, A ; в 0-й байт квадрата
ХСН Rl, A ; в 1-й байт квадрата
MUL AB ; произведение ст. байта на мл. байт
RLC A ; произведение удвоено
JNC sqrl ; переход по отсутствию переноса
INC R3 ; коррекция 3-го байта квадрата
MOV Rl, A ; в 1-й байт квадрата
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 ; четное число
Недостатком этой программы является существенная зависимость времени вычисления от значения аргумента. Кроме того, вычисленное значение корня всегда меньше истинного, то есть содержит систематическую погрешность.
Рассмотрим пример со значительно лучшими временными характеристиками. В отличие от рассмотренной программы займемся вычислением значения корня с округлением до ближайшего целого. Хорошо известное мнемоническое правило ускоренного вычисления квадрата целого десятичного числа, оканчивающегося на 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, то есть в среднем выполняется только четверть всех команд программы. Этот пример еще раз демонстрирует, что зачастую экономия времени вычисления может быть достигнута за счет затрат объема ПЗУ.
Для вычисления корня из числа, состоящего из двух байтов, можно использовать оба метода следующим образом. Для извлечения корня из старшего байта нужно приспособить второй вариант, изменив значения порогов таким образом, чтобы получить значение корня с недостатком. После вычисления старшей тетрады корня следует вычесть из исходного числа квадрат от приближенного значения корня и затем уточнить младшие цифры вычитанием нечетных чисел, первое из которых вычисляется по приближенному значению корня. Можно также использовать алгоритм извлечения корня «столбиком», которому во время оно обучали в школе. Автор намеренно не касается вычисления корня методом последовательных приближений, так как рекуррентная формула содержит операцию деления. Вычисления корня возможно и табличным методом с помощью интерполяции, но мы рассмотрим табличные методы вычисления далее, для других функций.
Как возвести в квадрат в ассемблере
Беззнаковые целые числа
Эта глава главным образом будет посвящена арифметическим операциям над большими беззнаковыми целыми числами (подробней о различных форматах чисел смотри в приложении Б). В приложениях на AVR-микроконтроллерах наиболее часто приходится использовать 16-разрядные вычисления, которые достаточно легко программируются. Двухбайтовые числа предоставляют достаточно широкий диапазон представления переменных. Однако, встречаются задачи в которых необходимо применение чисел и с большей разрядностью (счётчики импульсов, накопители суммы, промежуточные результаты вычислений и т.д.).
Реализовать многобайтовое сложение очень просто. Для этого имеется специальная команда adc Rd,Rr, которая складывает содержимое двух регистров и добавляет к полученной сумме бит переноса C из регистре SREG (Rd <- Rd+Rr+С). Этот бит устанавливается всегда, когда в результате предыдущей операции сложения возникает переполнение (т.е. бит C всегда является 9-ым битом результата операции сложения). Так может выглядеть сложение двух 16-разрядных чисел R17:R16 и R19:R18 (сумма размещается на месте второго слагаемого R19:R18):
add R18,R16 ;R18 <- R18 + R16
adc R19,R17 ;R19 <- R19 + R17 + C
Необходимо помнить, что в результате сложения двух n-разрядных чисел возможно образование n+1-разрядной суммы. Например, в результате следующей операции сложения получим:
0xB2FF + 0xCC45 = 0x17F44 = 0x10000 + 0x7F44.
Сумма двухбайтовых слагаемых превысила максимальное 16-разрядное значение 0xFFFF = 65535 и вместо 0x17F44 = 98116 мы получили 0x7F44 = 32580. При этом должен установиться флаг C (17-тый разряд суммы), как признак того, что произошел перенос в старший разряд и к полученному результату необходимо добавить 0x10000 = 65536.
В регистре SREG имеется еще один бит непосредственно связанный с действием сложения. Это флаг половинного переноса H, который может использоваться в 4-разрядных вычислениях. Он носит тот же смысл, что и флаг C, но указывает на переполнение суммы младших полубайтов (т.е. перенос из третьего в четвертый разряды числа). Флаг H почти никогда не используется на практике.
Если для хранения результата вычисления не хватает РОНов, то сложение рационально производить с помощью косвенной адресации, а результат размещать в SRAM процессора. В этом случае разрядность слагаемых и вычисленной суммы будет ограничена только свободным местом в памяти данных.
Подпрограмма такого сложения:
; [YH:YL] = [YH:YL] + [XH:XL]
; [YH:YL] – первое слагаемое при входе и сумма при
; выходе (косвенно адресуется через YH:YL)
; [XH:XL] – второе слагаемое (косвенно адресуется через XH:XL)
; R16,R17,R18 – вспомогательные регистры
; composed1 – адрес 1-го слагаемого и
; полученной суммы в ОЗУ
; composed 2 – адрес 2-го слагаемого в ОЗУ
; SIZE – размер слагаемых в байтах
; на выходе в C находится старший разряд результата
ldi YH, high (composed1) ;заносим в указатель Y адрес
ldi YL, low (composed1) ;первого слагаемого composed1
ldi XH, high (composed2) ;заносим в указатель Y адрес
ldi XL, low (composed2) ;второго слагаемого composed2
clc ;при первом входе в цикл C=0
ld R18,Y ;поочерёдно складываем с учётом переноса
adc R18,R17 ;все байты слагаемых и заносим результат
st Y+,R18 ;по адресу первого слагаемого
brne ad1 ;повторяем сложение SIZE раз
Подобно сложению с переносом в архитектуре AVR существует и команда вычитания с заемом sbc Rd,Rr. Для связи байтов в ней тоже участвует флаг C, который в этом случае обычно называется флагом заема. Бит C устанавливается каждый раз, когда результат предыдущей операции вычитания оказывается меньше нуля и автоматически вычитается из разности полученной после команды sbc Rd,Rr (Rd <- Rd-Rr-С). Ниже показан пример вычитания 16-разрядного числа R17:R16 из R19:R18 (разность помещается на место вычитаемого):
sub R18,R16 ;R18 <- R18 — R16
sbc R19,R17 ;R19 <- R19 — R17 — C
Разрядность разности при вычитании никогда не превысит разрядности делимого. Однако здесь возникает другая проблема, связанная с тем, что уменьшаемое может оказаться меньше вычитаемого. В результате такого действия мы получим установленный флаг C, как признак отрицательного результата. И хотя с точки зрения арифметики такая операция является вполне законной — она приводит к отрицательным числам, представленным в дополнительном коде, которые будут рассмотрены в следующем разделе.
Ниже приведена подпрограмма вычитания двух многобайтовых чисел, размещенных в SRAM.
; [YH:YL] = [YH:YL] — [XH:XL]
; [YH:YL] – уменьшаемое при входе и разность при
; выходе (косвенно адресуется через YH:YL)
; [XH:XL] – вычитаемое (косвенно адресуется через XH:XL)
; R16,R17,R18 – вспомогательные регистры
; reduced — адрес уменьшаемого и
; полученной разности в ОЗУ
; subtracted — адрес вычитаемого в ОЗУ
; SIZE – размер уменьшаемого и вычитаемого в байтах
; на выходе бит C=1 если [YH:YL] < [XH:XL]
ldi YH, high (reduced) ;заносим в указатель Y адрес
ldi YL, low (reduced) ;уменьшаемого reduced
ldi XH, high (subtracted) ;заносим в указатель X адрес
ldi XL, low (subtracted) ;вычитаемого subtracted
clc ;при первом входе в цикл C=0
ld R18,Y ;поочерёдно вычитаем с учётом заёма из
sbc R18,R17 ;уменьшаемого все байты вычитаемого и
st Y+,R17 ;заносим результат по адресу уменьшаемого
brne sb1 ;повторяем вычитание SIZE раз
У микроконтроллеров AVR, по сути, имеется два пути реализации умножения, разница между которыми заключается в форме представления произведения и, соответственно, в различии выполняемых арифметических операций. Первый оптимизирован для использования с командой однобайтового умножения, второй – использует только сложение и сдвиговые операции. Для произведения n-разрядного множимого и m-разрядного множителя необходимо отводить n+m разрядов.
Помимо этого существует особый случай умножения на целую степень 2. Всё дело в том, что 2 является основанием двоичной системы, а в любой позиционной системе операция умножения числа на основание системы приводит к увеличению веса каждого его разряда на порядок:
2*X = 2*(x n-1 *2 n-1 + x n-2 *2 n-2 + … + x 1 *2 1 + x 0 *2 0 ) = x n-1 *2 n + x n-2 *2 n-1 + … + x 1 *2 2 + x 0 *2 1 .
Как видно, коэффициенты xn числа X переместились на один разряд влево (x 0 стал при 2 1 , x 1 стал при 2 2 и т.д.). Итак, для умножения двоичного числа на 2 n необходимо просто сдвинуть его на n разрядов влево. Так можно осуществить умножение на 2 двухбайтового числа в регистрах R17:R16 посредством сдвиговых операций:
lsl R16 ;R16 <- R16 << 1 (LSB <- 0, флаг С <- MSB)
rol R17 ;R17 <- R17 << 1 (LSB <- флаг С, флаг С <- MSB)
Тот же результат можно получить, складывая число с самим собой:
Благодаря тому, что операции сдвига и сложения выполняются за одинаковое время (1 машинный цикл) оба примера равноценны.
Иногда встречаются операции умножения на число, которое близко к степени 2. В таких случаях намного проще заменить его суммой двух слагаемых, одно из которых кратно 2 n , и использовать только операции сдвига и сложения (вычитания):
63*X = (2 6 -1)*X = 2 6 *X — X = X<<6 – X,
33*X = (2 5 +1)*X = 2 5 *X + X = X<<5 + X,
130*X = (2 7 +2)*X = 2 7 *X + 2*X = X<<7 + X<<2.
Для умножения 2-байтовых чисел (обозначим их как XH:XL = 28*XH + XL и YH:YL = 28*YH + YL) применяется следующая вычислительная схема:
XH:XL * YH:YL = (2 8 *XH + XL)*(28*YH + YL) = 2 16 *XH*YH + 2 8 *(XH*YL + YH*XL) + XL*YL.
Рис.1 Вычислительная схема для умножения двухбайтовых чисел с использованием инструкции умножения
Отыскание 32-разрядного результата сводится к последовательности операций однобайтовых умножений и последующего сложения всех произведений с учётом сдвига слагаемых XH*YL, XL*YH на 1 байт и XH*YH на 2 байта, как показано на рис.1. Подпрограмма, реализующая эти действия, приведена ниже. Напомним, что произведение двух однобайтовых множителей, полученное в результате выполнения команды mul Rd,Rr или любой другой команды умножения, всегда заносится в регистровую пару R1:R0.
; R23:R22:R21:R20 = R17:R16 * R19:R18
; R1,R0 – вспомогательные регистры
mul R16,R18 ;находим XL*YL = R16*R18 и заносим его в
movw R20,R0 ;младшие байты произведения R21:R20
mul R17,R19 ;находим XH*YH = R17*R19 и заносим его в
movw R22,R0 ;старшие байты произведения R23:R22
mul R17,R18 ;находим XH*YL = R17*R18 и прибавляем его к
clr R17 ;байтам R23:R22:R21 произведения
mul R16,R19 ;находим YH*XL = R19*R16 и прибавляем его к
add R21,R0 ;байтам R23:R22:R21 произведения
Возвести двухбайтовое число в квадрат еще проще:
XH:XL * XH:XL = (2 8 *XH + XL)*(2 8 *XH + XL) = 2 16 *XH*XH + 2 8 *2*XH*XL + XL*XL.
Подпрограмма возведения в квадрат приведена ниже. Она является хорошим примером того, где может пригодиться инструкция fmul Rd,Rr, которая одним действием производит умножение двух однобайтовых чисел и сдвиг произведения на 1 разряд влево.
; R21:R20:R19:R18 = R17:R16 * R17:R16
; R17:R16 – число, возводимое в квадрат
; R1,R0 – вспомогательные регистры
mul R16,R16 ;находим XL*XL = R16*R16 и заносим его в
movw R18,R0 ;младшие байты произведения R19:R18
mul R17,R17 ;находим XH*XH = R17*R17 и заносим его в
movw R20,R0 ;старшие байты произведения R21:R20
fmul R17,R16 ;находим 2*XH*YL = R17*R18 и прибавляем его
clr R17 ;к байтам R21:R20:R19 произведения
Во многих случаях команда fmul Rd,Rr позволяет использовать аппаратный умножитель 8×8 фактически как умножитель 9×8 с получением 17-разрядного результата (MSB произведения размещается в C). Это бывает очень полезно, когда возникает необходимость умножить переменную на постоянный числовой коэффициент, который немного выходит за пределы 8-разрядной сетки. Так, допустим, можно умножить число из R16 на 500
ldi R17,250 ;R1:R0 <- (250<<1)*R16 = 500*R16
fmul R17,R16 ; флаг С <- MSB
ldi R17,250 ;R1:R0 <- (250<<2)*R16 = 1000*R16
fmul R17,R16 ;флаг С <- MSB
Ниже показан другой практически важный пример умножения, когда один из множителей (множитель X) однобайтовый. В основе подпрограммы лежит следующая вычислительная схема:
X * YH:YL = X*(2 8 *YH + YL) = 2 8 *X*YH + X*YL
; R21:R20:R19 = R18 * R17:R16
; R1,R0 – вспомогательные регистры
mul R18,R17 ;находим X*YH = R18*R17 и заносим его в
movw R20,R0 ;старшие байты произведения R21:R20
mul R18,R16 ;находим X*YL = R18*R16
add R19,R0 ;и прибавляем его
add R20,R1 ;к произведению R21:R20:R19
Точно также могут быть разложены числа и с большей разрядностью. Однако с ростом их величины начинают резко возрастать и затраты ресурсов процессора. Так для умножения трёхбайтовых чисел понадобится по 9 операций однобайтовых умножений и двухбайтовых сложений; для четырёхбайтовых уже по 16 операций и т.д.
В подобных случаях необходимо использовать другой, наиболее общий алгоритм, который не использует команду mul Rd,Rr. А для микроконтроллеров семейства ATtiny, (а также для устаревшей линейки моделей Classic), у которых отсутствует аппаратный умножитель, он вообще является единственно возможным.
Для пояснения алгоритма, перепишем произведение Z двух произвольных двоичных чисел
Произведение X*y j называется частичным произведением (X*y j = X при y j =1 и X*y j = 0 при y j =0), а произведение (X*y j )*2 j есть не что иное, как частичное произведение, сдвинутое на j разрядов влево. Итак, нахождение произведение X*Y сводится к нахождению суммы частичных произведений X*y j , каждое из которых в свою очередь сдвинуто на j разрядов влево соответственно. На этом принципе основан школьный метод умножения в столбик. Рассмотрим пример умножения двух 4-разрядных чисел:
Как видим, для получения результата используются только операции сложения и сдвига. При этом в тех разрядах Y, где y j =0 и X*y j =0. И если предварительно анализировать значения y j/, то можно пропускать пустое сложение с 0 в соответствующих итерациях. Ниже приведена подпрограмма умножения двух трёхбайтовых чисел. В ней для получения суммы частичных произведений, сдвинутых каждое на j разрядов влево, производится сдвиг накопителя произведений m=24 раза вправо, а для экономии памяти младшие 3 байта произведения заносятся в те же регистры, где находился множитель.
; R24:R23:R22:R21:R20:R19 = R18:R17:R16 * R21:R20:R19
; R25,R1,R0 – вспомогательный регистр
clr R22 ;очищаем регистры R22,R23,R24
clr R23 ;при входе в подпрограмму
ldi R25,24 ;инициализируем счётчик циклов сложения
clc ;сдвинутых частичных произведений
ml1: sbrs R19,0 ;если младший бит множителя 1, то
add R22,R16 ;добавляем к накопителю очередное
adc R23,R17 ;частичное произведение R18:R17:R16
ml2: ror R24 ;байтам R24:R23:R22 накопителя произведения
ror R23 ;в ином случае пропускаем это действие
ror R22 ;и переходим к очередному сдвигу множителя
dec R25 ;повторяем m=24 раз цикл сложения
brne ml1 ;сдвинутых частичных произведений
Из всех арифметических операций деление занимает особое место. По отношению к умножению деление является обратной операцией и не имеет конечной формулы для определения частного. Деление – единственная арифметическая операция ограниченной точности! Не смотря на это алгоритмы деления достаточно просты. Ниже будут показаны два таких алгоритма, которые используют только операции вычитания и сдвигов. Для того чтобы получить результат в виде целочисленных частного и остатка нужно предварительно убедиться в том, чтобы делимое было больше делителя и, конечно, исключить возникновение запрещённой операции деления на 0. При делении n-разрядного делимого на m-разрядный делитель под частное необходимо отвести n, а под остаток m разрядов.
Частным случаем является деление на целую степень 2:
X/2 = (x -1 *2 n-1 + x n-2 *2 n-2 + … + x 1 *2 1 + x 0 *2 0 )/2 = x n-1 *2 n-1 + x n-2 *2 n-2 + … + x 1 *2 0 + x 0 *1/2 1
Все коэффициенты x n двоичного числа X переместились на один разряд вправо (x 0 стал при 1/2 1 , x 1 стал при 2 0 и т.д.). Таким образом для деления двоичного числа на 2 n необходимо произвести сдвиг его содержимого на n разрядов в правую сторону. Так выглядит деление на 2 16-разрядного числа в регистрах R17:R16:
lsr R17 ; R17 <- R17 >> 1 (MSB <- 0, флаг С <- LSB)
ror R16 ; R16 <- R16 >> 1 (MSB <- С, флаг С <- LSB)
Обратите внимание на то, что после сдвига вправо во флаге переноса С окажется целочисленный остаток (младший коэффициент x0) от деления на 2.
Для другого частного случая деления на 3 существует один очень интересный алгоритм, основанный на разложении дроби X/3 в ряд вида:
X/3 = X/2 — X/4 + X/8 — X/16 + X/32 — …
Каждый член ряда получается делением X на целую степень 2, что как было показано выше, легко реализуется сдвиговыми операциями. Ниже приведена подпрограмма деления на 3 16-разрядного числа.
; R20 – вспомогательный регистр
clr R18 ;очищаем вспомогательные регистры R18,R19
clr R19 ;при входе в подпрограмму
du1: rcall shft_right
brne PC+2 ;если Z=1,
ret ;то завершаем деление
add R18,R16 ;в ином случае добавляем к накопителю
adc R19,R17 ;очередной нечётный член ряда
brne PC+2 ;если Z=1,
ret ;то завершаем деление
sub R18,R16 ;в ином случае вычитаем из накопителя
sbc R19,R17 ;очередной чётный член ряда
lsr R17 ;производим деление R17:R16 / 2,
ror R16 ;получая очередной член ряда
mov R20,R17 ;если R20 = R17+R16 = 0 (т.е. R17:R16=0),
or R20,R16 ;то выходим из подпрограммы с флагом Z=1
Этот пример очень эффективен. Его быстродействие ограничено только разрядностью делимого. Более того для делимого произвольной величины обрабатывается оптимальное число членов ряда (до 16), а результат автоматически округляется до ближайшего целого числа.
Естественно, что в тех случаях, когда необходимо разделить число на 6 можно совместно использовать приемы деления на 2 и 3:
Для уменьшения погрешности деление чётных чисел следует начинать с деления на 2 (остаток 0) а, деление нечётных с деления на 3 (алгоритм этого вида деления учитывает остаток).
В общем случае самый естественный и простой способ разделить одно число на другое – это решить уравнение, вытекающее непосредственно из определения операции деления:
где X – делимое, Y – делитель, Z – частное, R – целочисленный остаток от деления.
Уравнение содержит два неизвестных параметра Z и R и поэтому не может быть явно разрешено. Для отыскания результата необходимо прибегнуть к итерационному методу: вычитать из делимого делитель до тех пор, пока остаток не окажется меньше делителя. Тогда число циклов вычитания численно даст частное Z, а остаток будет равен целочисленному остатку R от деления. Для примера, произведем следующее деление:
X — Z*Y = R, 213 – 21*10 = 3,
Мы 21 раз смогли вычесть из 213 по 10 пока не образовался остаток 3<10. Приведённый алгоритм имеет существенный недостаток – скорость его выполнения напрямую зависит от величины частного (числа итераций вычитания), что делает нежелательным его использование для деления больших чисел. Применяется он, в основном, в задачах ограниченных делением однобайтовых величин. Подпрограмма деления:
; R17 – делимое при входе и целочисленный остаток на выходе
clr R18 ;очищаем R18 при входе
sub R17,R16 ;производим вычитание R17-R16
brcc PC-2 ;до тех пор пока разность R17-R16 > 0
dec R18 ;когда разность R17-R16 < 0
add R17,R16 ;восстанавливаем R17 и корректируем R18
Для чисел большей разрядности необходимо использовать способ деления, основанный на приведенной ниже вычислительной схеме. Для этого представим необходимо выражение операции деления в следующем виде:
Нахождение частного сводится к отысканию его коэффициентов z i , которые определяются, согласно формуле, следующим образом: необходимо последовательно сравнивать X с произведениями Y*2 i и если X > Y*2 i , то в этом случае необходимо произвести вычитание Y*2 i из X, а соответствующий разряд z i установить в 1; если X < Y*2 i – вычитание пропускается и в этой итерации z i =0. Эта процедура продолжается до тех пор, пока не останется остаток Ri получаются простым сдвигом Y на i разрядов влево. Аналогично производится деление в любой позиционной системе (метод деления в столбик), но проще всего в двоичной из-за того, что в X может содержаться Y*2 i максимум один раз (на что и указывает единица в соответствующем разряде). Рассмотрим пример деления:
Необходимо обратить внимание на то, что число итераций сравнения должно совпадать с числом значащих разрядов частного (в данном случае n=4 для определения z 0 …z 3 ). Однако разрядность частного заранее никогда не известна и поэтому всегда необходимо знать максимально возможную разрядность результата деления. На практике чаще всего используют вычисления, в которых частное заведомо умещается в 8,16,24 бита (кратно одному байту) и т.д. При этом нужно использовать 8,16,24 итераций сравнения X с Y*2 i , соответственно. С целочисленным остатком R проблем не возникает – его размер ограничен разрядностью Y (R < Y).
Подпрограмма деления двухбайтового числа на однобайтовое приведена ниже. В ней для сравнения X с Y*2 i (i ∈ <0,…,15>) вместо сдвига делителя Y на n разрядов вправо используется поочерёдный сдвиг делимого на n разрядов влево, а для экономии памяти частное записывается на тоже место, что и делимое. В начале программы осуществляется проверка условия Y ≠ 0, без которого деление не может быть корректно осуществлено.
Как возвести в квадрат в ассемблере
Сопроцессор Neon позволяет выполняеть одновременно несколько операций. Сопроцессор Neon работает с теми же регистрами, что и FPU, но позволяет также полностью задействовать 32 128-разрядных регистра, которые называются V0 , V1 , V2 , . V31
Стоит отметить, что сопроцессор NEON может помещать в эти регистры также и 128-разрядные целые числа, в этом случае регистры именуются Q0 , . Q31 .
Но также сопроцессор Neon может обращаться к младшим 64 бит регистров Vn — 64-разрядным регистрам D0 — D31 .
Neon может работать как с числами с плавающей точкой, так и с целыми числами.
Сопроцессор Neon применяет концепцию дорожек/аллей (lane) для всех своих операций. Когда выбирается тип данных, процессор рассматривает регистр как разделенный учитывает на некоторое количество дорожек — одна дорожка для каждого объекта данных. Например, если мы работаем с 32-разрядными целыми числами и используем 128-разрядный регистр V , то регистр считается разделенным на четыре дорожки, по одной для каждого целого 32-разрядного числа. То есть мы можем поместить в 128-разрядный регистр 4 32-разрядных числа, и над каждым из этих чисел операции будут идти параллельно.
Арифметические операции
Сопроцессор Neon применяет все те же арифметические операции, которые доступны в ARM64 для целых чисел и чисел с плавающей точкой. Например, возьмем операцию сложения, которая имеет две формы: одна для сложения целых чисел ( ADD ) и одна для сложения чисел с плавающей точкой ( FADD
T представляет спецификатор, через который передается тип и размер используемых данных. Данный спецификатор может иметь следующие значения
Для операций с целыми числами (например, для инструкции ADD ) может принимать значения 8B, 16B, 4H, 8H, 2S, 4S и 2D
Для операций с числами с плавающей точкой (например, для инструкции FADD ) может принимать значения 4H, 8H, 2S, 4S и 2D
Рассмотрим небольшой пример. Допустим, нам надо возвести в квадрат четыре числа, пусть это будут числа .single. Для этого определим следующую программу:
Итак, в секции .data под меткой numbers определены четыре числа single.
В программе сначала загружаем адрес метки numbers в регистр X20, а затем все числа в регистр Q0 (он же регистр V0 ).
Числа загружаются в регистры по порядку, то есть в S0 будет первое число 1, в S1 — второе число 2 и так далее.
Далее выполняем возведение в квадрат, то есть умножаем каждое число на себя:
Выражение V0.4S указывает на 4 значения типа single в регистре V0 , то есть берем каждое число single и умножаем его на себя. Причем все четыре числа будут умножаться друг на друга одновременно. Таким образом, для умножения 4-х 32-разрядных чисел друг на друга нам потребуется всего одна инструкция. Ситуация после умножения
Далее сохраняем полученные числа обратно из V0 по адресу в X0, то есть в numbers.
Затем в цикле выводим каждое из четырех числе на консоль с помощью функции printf языка C (Соответственно для компиляции применяется компилятор gcc). В итоге после компиляции программы и ее запуска на консоль будут выведены квадраты числе
Другой пример — сложение чисел. Определим следующую программу:
Здесь мы собираемся сложить по парно числа numbers1 с числами numbers2 и результат сохранить в numbers3.
В программе загружаем в регистр X20 адрес метки numbers1 и затем загружаем numbers1 в V0 , а numbers2 в V1 :
При этом увеличиваем адрес в X20 на 8 * 4 = 32 байта, то есть после этого X20 указывает на адрес метки numbers3. И загружаем эти числа в регистр V2
Затем складываем числа в соответствующих дорожках в V0 и V1 и результат помещаем в регистр V2 . В итоге опять регистры V0, V1, V2 будут разбиты на 4 дорожки, и вычисление суммы чисел из соответствующих дорожек будет производиться параллельно.
Консольный вывод программы:
Аналогичным образом мы можем работать и с другими типами данных, например, с целыми числами типа word , то есть 32-разрядными числами:
Доступ к дорожкам
Для доступа к значению в определенной дорожке применяются квадратные скобки, в которых указывается номер дорожки:
Отсчет дорожек начинается с нуля. Например:
Здесь числа во всех 4 дорожках регистра V1 умножаются на число в первой дорожке регистра V0, и результат — полученные 4 числа после умножения помещаются в 4 дорожки регистра V2.
Возвести число в степень на этапе компиляции
Как в fasm возвести число в степень на этапе компиляции? Для других действий с числами, например, битового сдвига можно написать так: mov ax, 10 shl constant , но код mov ax, 10 pow constant , не компилируется.
Написал макрос pow , получается немного костыльно, но работает:
Результат компиляции в 16-ричном виде:
Видим 0186A0h (100000 в десятичной системе) два раза, что и требовалось.
Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.3.11.43304
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.