Деление

Деление

Из всех арифметических операций деление занимает особое место. По отношению к умножению деление является обратной операцией и не имеет конечной формулы для определения частного. Деление – единственная арифметическая операция ограниченной точности! Не смотря на это алгоритмы деления достаточно просты. Ниже будут показаны два таких алгоритма, которые используют только операции вычитания и сдвигов. Для того чтобы получить результат в виде целочисленных частного и остатка нужно предварительно убедиться в том, чтобы делимое было больше делителя и, конечно, исключить возникновение запрещённой операции деления на 0. При делении n-разрядного делимого на m-разрядный делитель под частное необходимо отвести n, а под остаток m разрядов.

Частным случаем является деление на целую степень 2:

X/2 = (x-1*2n-1 + xn-2*2n-2 + … + x1*21 + x0*20 )/2 = xn-1*2n-1  + xn-2*2n-2 + … + x1*20 + x0*1/21

Все коэффициенты xn двоичного числа X переместились на один разряд вправо (x0 стал при 1/21, x1 стал при 20 и т.д.). Таким образом для деления двоичного числа на 2n необходимо произвести сдвиг его содержимого на n разрядов в правую сторону. Так выглядит деление на 2 16-разрядного числа в регистрах R17:R16:

lsr R17 ; R17> 1 (MSB> 1 (MSB

Обратите внимание на то, что после сдвига вправо во флаге переноса С окажется целочисленный остаток (младший коэффициент x0) от деления на 2.

Для другого частного случая деления на 3 существует один очень интересный алгоритм, основанный на разложении дроби X/3 в ряд вида:

X/3 = X/2 – X/4 + X/8 – X/16 + X/32 – …

Каждый член ряда получается делением X на целую степень 2, что как было показано выше, легко реализуется сдвиговыми операциями. Ниже приведена подпрограмма деления на 3 16-разрядного числа.

; R19:R18 = R17:R16/3 ; R19:R18 – частное ; R17:R16 – делимое ; R20 – вспомогательный регистр div16to3: clr R18 ;очищаем вспомогательные регистры R18,R19 clr R19 ;при входе в подпрограмму du1: rcall shft_right brne PC+2 ;если Z=1, ret ;то завершаем деление add R18,R16 ;в ином случае добавляем к накопителю adc R19,R17 ;очередной нечётный член ряда rcall shift_right brne PC+2 ;если Z=1, ret ;то завершаем деление sub R18,R16 ;в ином случае вычитаем из накопителя sbc R19,R17 ;очередной чётный член ряда rjmp du1 shft_right: lsr R17 ;производим деление R17:R16 / 2, ror R16 ;получая очередной член ряда mov R20,R17 ;если R20 = R17+R16 = 0 (т.е. R17:R16=0), or R20,R16 ;то выходим из подпрограммы с флагом Z=1 ret

Этот пример очень эффективен. Его быстродействие ограничено только разрядностью делимого. Более того для делимого произвольной величины обрабатывается оптимальное число членов ряда (до 16), а результат автоматически округляется до ближайшего целого числа.

Естественно, что в тех случаях, когда необходимо разделить число на 6 можно совместно использовать приемы деления на 2 и 3:

X/6 = (X/2)/3 = (X >> 1)/3 = (X/3) >> 1

Для уменьшения погрешности деление чётных чисел следует начинать с деления на 2 (остаток 0) а, деление нечётных с деления на 3 (алгоритм этого вида деления учитывает остаток).

В общем случае самый естественный и простой способ разделить одно число на другое – это решить уравнение, вытекающее непосредственно из определения операции деления:

X = Z*Y + R,

R < Y, Y ≠ 0,

где X – делимое, Y – делитель, Z – частное, R – целочисленный остаток от деления.

Уравнение содержит два неизвестных параметра Z и R и поэтому не может быть явно разрешено. Для отыскания результата необходимо прибегнуть к итерационному методу: вычитать из делимого делитель до тех пор, пока остаток не окажется меньше делителя. Тогда число циклов вычитания численно даст частное Z, а остаток будет равен целочисленному остатку R от деления. Для примера, произведем следующее деление:

X = 213, Y = 10,

X – Z*Y = R, 213 – 21*10 = 3,

Z = 21, R = 3.

Мы 21 раз смогли вычесть из 213 по 10 пока не образовался остаток 3<10. Приведённый алгоритм имеет существенный недостаток – скорость его выполнения напрямую зависит от величины частного (числа итераций вычитания), что делает нежелательным его использование для деления больших чисел. Применяется он, в основном, в задачах ограниченных делением однобайтовых величин. Подпрограмма деления:

; [R18] + {R17} = R17 / R16 ; R18 – частное ; R17 – делимое при входе и целочисленный остаток на выходе ; R16 – делитель div8_8: clr R18 ;очищаем R18 при входе sub R17,R16 ;производим вычитание R17-R16 inc R18 brcc PC-2 ;до тех пор пока разность R17-R16 > 0 dec R18 ;когда разность R17-R16 < 0 add R17,R16 ;восстанавливаем R17 и корректируем R18 ret

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

Нахождение частного сводится к отысканию его коэффициентов zi, которые определяются, согласно формуле, следующим образом: необходимо последовательно сравнивать X с произведениями Y*2i и если  X > Y*2i, то в этом случае необходимо произвести вычитание Y*2i из X, а соответствующий разряд zi установить в 1; если X < Y*2i – вычитание пропускается и в этой итерации zi=0. Эта процедура продолжается до тех пор, пока не останется остаток R<Y. Произведения Y*2i получаются простым сдвигом Y на i разрядов влево. Аналогично производится деление в любой позиционной системе (метод деления в столбик), но проще всего в двоичной из-за того, что в X может содержаться Y*2i максимум один раз (на что и указывает единица в соответствующем разряде). Рассмотрим пример деления:

Необходимо обратить внимание на то, что число итераций сравнения должно совпадать с числом значащих разрядов частного (в данном случае n=4 для определения z0…z3). Однако разрядность частного заранее никогда не известна и поэтому всегда необходимо знать максимально возможную разрядность результата деления. На практике чаще всего используют вычисления, в которых частное заведомо умещается в 8,16,24 бита (кратно одному байту) и т.д. При этом нужно использовать 8,16,24 итераций сравнения X с Y*2i, соответственно. С целочисленным остатком R проблем не возникает – его размер ограничен разрядностью Y (R < Y).

Подпрограмма деления двухбайтового числа на однобайтовое приведена ниже. В ней для сравнения X с Y*2i (i ∈ {0,…,15}) вместо сдвига делителя Y на n разрядов вправо используется поочерёдный сдвиг делимого на n разрядов влево, а для экономии памяти частное записывается на тоже место, что и делимое. В начале программы осуществляется проверка условия Y ≠ 0, без которого деление не может быть корректно осуществлено.

; [R17:R16] + {R18} = R17:R16 / R20 ; R17:R16 – делимое при входе и частное на выходе ; R20 – делитель ; R18 – целочисленный остаток ; R21, R22 – вспомогательные регистры ; при выходе из подпрограммы в C находится признак ошибки ; если C = 1 – произошла ошибка (R20 = 0) ; если С = 0 – деление успешно выполнено div16_8: tst R20 ;если R20=0 выходим из подпрограммы breq dv3 ;с признаком ошибки C=1 clr R18 ;очищаем регистры R18,R19,R21 при clr R19 ;входе в подпрограмму clr R21 ldi R22,16 ;инициализируем счётчик циклов dv1: lsl R16 ;сдвигаем делимое R17:R16 со rol R17 ;вспомогательными регистрами rol R18 ;R19,R18 на один разряд влево rol R19 sub R18,R20 ;осуществляем пробное вычитание sbc R19,R21 ;R19:R18 – R20 и если R19:R18 > R20, ori R16,0x01 ;то устанавливаем zi=1 brcc dv2 add R18,R20 ;в ином случае восстанавливаем делимое adc R19,R21 andi R16,0xFE ;и устанавливаем zi=0 dv2: dec R22 brne dv1 ;повторяем цикл n=16 раз clc ;успешно завершаем подпрограмму ret ;со флагом С=0 dv3: sec ;выходим из-за ошибки ret ;с флагом С=1

Ниже приведена еще одна важная подпрограмма, реализующая  деление 4-хбайтового числа на двухбайтовое с получением 16-разрядных частного и остатка. По своей структуре она аналогична предыдущей, кроме того, что при входе в подпрограмму производится проверка на переполнение результата и тем самым исключаются случаи, при которых частное может не умещаться в отведённых 2-х байтах (например, X = 0x51F356D, Y = 0x100, R = 0x6D, Z = 0x51F35 – имеет разрядность более 16 бит).

; [R17:R16] + {R21:R20} = R19:R18:R17:R16 / R23:R24 ; R17:R16 – частное ; R21:R20 – целочисленный остаток ; R19:R18:R17:R16 – делимое ; R23:R24– делитель ; R25,R26 – вспомогательный регистр ; при выходе из подпрограммы в C находится признак ошибки ; если C = 1 – произошла ошибка (R23:R24 = 0 или размер ; частного больше 2 байт) ; если С = 0 – деление успешно выполнено div32_16: mov R20,R23 ;если R20 = R23 + R24 = 0 or R20,R24 ;(т.е. R24:R23 = 0), то выходим из breq dv3 ;подпрограммы с признаком ошибки C=1 cp R18,R23 ;если R19:R18 < R24:R23 cpc R19,R24 ;(т.е.частное больше 2-х байт), то выходим brcc dv3 ;из подпрограммы с признаком ошибки C=1 clr R20 ;очищаем регистры R20,R21,R22,R25 clr R21 ;при входе в подпрограмму clr R22 clr R25 ldi R26,32 ;инициализируем счётчик циклов dv1: lsl R16 ;сдвигаем делимое R19:R18:R17:R16 со rol R17 ;вспомогательными регистрами R20, R21, R22 rol R18 ;на один разряд влево rol R19 rol R20 rol R21 rol R22 sub R20,R23 ;осуществляем пробное вычитание sbc R21,R24 ;R22:R21:R20 – R24:R23 и если sbc R22,R25 ;R22:R21:R20 > R24:R23, ori R16,0x01 ;то устанавливаем zi=1 brcc dv2 add R20,R23 ;в ином случае восстанавливаем делимое adc R21,R24 adc R22,R25 andi R16,0xFE ;и устанавливаем zi=0 dv2: dec R26 ;повторяем n=32 раза цикл brne dv1 ;сравнения R20:R19:R18 с R22:R21 clc ;успешно завершаем подпрограмму ret ;с флагом С=0 dv3: sec ;выходим из-за ошибки ret


Категория: Микроконтроллеры
Метки:

Написать коментарий

*
= 3 + 1

Добавить изображение

Последние статьи