Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Целочисленное деление с восстановлением остатка

Рассмотрим тривиальный случай деления столбиком в десятичной арифметике.

-    
     
-          
         
  -        
         
               

В примере деления представляет интерес взаимное расположение цифр делимого и произведения делителя 25 на старшую цифру частного равную 1. Взаимное расположение указанных цифр показывает, что в первом вычитании изображение 25 (выделено полужирным курсивом) задает число 2500 и это число получено умножением делителя 25 на цифру 1. Значит, к моменту умножения делителя на цифру 1 начальное значение делителя равное 25 было увеличено в 100 раз, что соответствует сдвигу цифр делителя влево на 2 десятичных разряда. Кроме того, это означает, что цифра 1 находится в разряде сотен.

Таким образом, процесс деления предполагает необходимость сдвига влево заданного (исходного) кода делителя. Величина этого сдвига определяет номер разряда в изображении частного, которому принадлежит первая (старшая) цифра частного. В примере цифра 1 частного принадлежит разряду сотен.

Заметим, что при делении столбиком первоначальный сдвиг делителя выбирается с учетом двух критериев.

Во-первых, полученное после сдвига новое значение делителя должно быть не больше значения делимого.

Во-вторых, делимое должно превосходить новый делитель не более, чем в 9 раз, поскольку 9 – старшая цифра десятичной арифметики.

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

Отмеченные факты учтем при разработке алгоритма деления.

 

Алгоритм 6.5. Целочисленноеделение с восстановлением остатка со сдвигом делителя вправо.

Даны: коды A и B чисел на РСЦБЗn.

Поскольку предполагается РС с фиксированным положением позиционной точки, то ограничимся рассмотрением алгоритма деления, дающего в качестве результата целую часть частного A/B. Такую операцию целочисленного деления обозначим как div.

Таким образом, требуется вычислить частное C = A div B.

В процессе деления необходимо вычитать делитель из текущего значения остатка делимого. Поэтому необходимо иметь (-B)ДК, то есть дополнительный код числа (-B). Таким образом, делитель должен быть представлен двумя кодами. При этом, по причине отсутствия знакового разряда в рассматриваемой РС, достаточно иметь цифровую часть кода (-B)ДК.

Обозначим:

i – величина сдвига кода делителя влево относительно его первоначального (заданного) вида;

D – цифровая часть от (-B)ДК;

p – значение переноса из старшего разряда РС (перенос в предполагаемый разряд знака) при суммировании кодов A и D.

 

1. Подготовка переменных:

1.1. C:= 0 (- задание начального значения кода частного)

1.2. i:= 0 (- задание начального значения величины сдвига делителя)

2. Начальный сдвиг кода делителя

2.1. Если bn-1 =0, топерейти к 2.2, иначеперейти к 3

2.2. Сдвиг кода делителя влево на 1 разряд с целью удаления из РС делителя незначащего нуля:

B:= L1(B· 0); (- сдвиг кода делителя влево на 1 разряд)

i := i+1; (- код делителя сдвинут влево еще на один разряд)

2.3. Перейти к 2.1

3. D:= nota(B)+1; (- формирование цифровой части от (-B)ДК; nota(B) обозначает операцию поразрядного инвертирования кода B)

4. Цикл формирования кода частного:

4.1. Предполагаем, что очередная цифра частного равна 1, поэтому уменьшаем остаток (в начальном состоянии остаток равен делимому) на величину делителя. При суммировании кодов фиксируем значение переноса p из старшего разряда РС:

A:= A+D (- это означает A:= AB, но только без разряда знака)

4.2. Поскольку на шаге 4.1 предполагается суммирование чисел с разными знаками, то значение p=0 сигнализирует о получении отрицательной разности, что говорит об ошибочности предположения о значении очередной цифры частного. Значение p=1 сигнализирует о правильности предположения о значении цифры частного. В обоих случаях оказывается, что очередная цифра частного совпадает со значением переноса p. Поэтому:

C:= L1(C· p); (- занесение очередной цифры в код частного)

4.3. Если p = 0, то A:= A+B (- восстановление остатка, то есть возврат к значению A, имевшему место до шага 4.1)

4.4. Сдвиг кодов B и D делителя вправо на 1 разряд:

B:= R1(0· B);

D:= R1(1· D);

(D – цифровая часть дополнительного кода отрицательного (!) числа, поэтому в крайний левый разряд кода D при его сдвиге вправо заносится цифра 1)

4.5. Если i = 0, топерейти к 5

4.6. i:= i -1

4.7. Перейти к 4.1

5. Конец алгоритма (Код C задает искомый результат от A div B)

 

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

Исполнение алгоритма можно в некоторых случаях ускорить, если после шага 1 предусмотреть анализ значения делимого на равенство нулю. Дополнительного ускорения алгоритма в некоторых частных случаях можно добиться, если после шага 4.7 принять меры к обнаружению нулевого значения очередного остатка. При этом в случае A=0 для получения искомого результата будет необходимо и достаточно, уменьшая значение переменной i до нуля, выполнить соответствующее количество раз сдвиг текущего кода частного влево.

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...