с II jc II у« 2{х II у) II Сдвиг влево на один бит

cje<-(cje) + (OW)z) Прибавление делителя end

Уо <-< II Установка одного бита частного

if с = 1 then x<x-¥i Корремщя отрицательного остатка

Микрокомпьютер 801 (ранняя экспериментальная RISC-разработка ШМ) имеет команду пошагового деления, которая, по суш, выполняет приведенные вьппе в теле цикла действия. Эта команда использует бит переноса для хранения с и MQ (32-биттовый регистр) для хранения у. Для реализации данной команды требуется 33-битовый сумматор и 32-битовое вычитающее устройство. Команда пошагового деления микрокомпьютера 801 несколько сложнее, чем действия, выполняемые в теле цикла, поскольку выполняет знаковое деление и оснащена проверкой переполнения. При ее использовании подпрограмма деления может быть записана с помощью 32 последовательных команд пошагового деления, за которыми следует коррекция частного и остатка (для того, чтобы обеспечить верный знак остатка).

Использование короткого деления

Алгоритм для деления 64+32 => 32 может быть получен из алгоритма беззнакового деления больших целых чисел в листинге 9.1 для частного случая т=4 и п=2. Кроме того, требуется внесение ряда других изменений. Параметры в данном случае должны представлять собой полные слова, передаваемые по значению, а не массивы полуслов. Условие переполнения также отличается от исходного; в данном случае переполнение происходит, если частное не помещается в полном слове. Все это дает возможность внести определенные упрощения в программу. Можно показать, что оценка qhat в данном случае всегда точная, так как делитель состоит только из двух цифр по полслова. Это означает, что корректирующий щаг с прибавлением делителя может быть опущен. Если развернуть "главный цикл" листинга 9.1 и цикл внутри него, становятся возможны еще некоторые небольшие упрощения кода.

Результат этих преофазований показан в листинге 9.3. Делимое находится в словах ul и иО; в ul содержится старшее слово. Параметр v содержит делитель. Функция по завершении вычислений возвращает значение частного. Если вызывающая функция передает в качестве г ненулевой указатель, то остаток будет возвращен в слове, на которое указывает г.

Листинг 9.3. Длинное беззнаковое деление с использованием команды деления полных слов

unsigned divlu(unsigned ul, unsigned uO, unsigned v, unsigned *r)

const unsigned b

{ устанавливается невозможное

if (г != NULL) значение остатка и

*г = OxFFFFFFFF; возвращается максимально

return OxFFFFFFFF; возможное число

S = nlz(v); О <= S <= 31.

V = V << S; Нормализация делителя

vnl = V >> 16; Разбиение делителя

vnO = V & OxFFFF; на две 16-битовые цифры ип32 = (ul « s) I (uO >> 32 - s) Sc i-s » 31);

unlO = uO << s; Сдвиг делимого влево

unl = unlO >> 16; Разбиение правой половины

unO = unlO Sc OxFFFF; делимого на две цифры

gl = un32/vnl; Вычисление первой цифры

rhat = un32 - ql*vnl; частного ql адаinl:

if (ql >= b I I ql*vnO > b*rhat + unl)

ql = ql - 1;

rhat = rhat + vnl;

if (rhat < b) goto againl;

un21 = un32*b + unl - ql*v; Умножение и вычитание qO = un21/vnl; Вычисление второй цифры

rhat = un21 - qO*vnl; частного qO

again2:

if (qO >= b I I qO*vnO > b*rhat + unO)

qO = qO - 1;

rhat = rhat + vnl;

if (rhat < b) goto again2;

if (r != NULL) Если требуется,

*r = (un21*b + unO вычисляем остаток

- qO*v) >> s; return ql*b + qO;

В качестве индикатора переполнения программа возвращает значение остатка, равное максимально возможному целому числу. Такой остаток невозможен ни при каком корректном делении, поскольку остаток всегда меньше делителя. Кроме того, при переполнении функция возвращает частное, равное максимально возможному целому числу (что также может служить индикатором переполнения в случае, когда вызывающая функция не запрашивает значение остатка).

Странное выражение (-s>>3i) в присвоении из 2 предназначено для того, чтобы программа работала в случае s = о на машинах, сдвиг у которых выполняется по модулю 32 (например, в Intel х86).

Эксперименты с равномерно распределенными случайными числами показывают, что тело цикла again выполняется примерно около 0.38 раза на каждый вызов функции. Это дает нам среднее количество выполняемых команд, равное 52. Среди них одна команда подсчета количества ведущих нулевых битов, две - деления, а также 6.5 - умножения (не считая умножений на ь, которые выполняются при помощи сдвигов). Если требуется значение остатка, добавляется шесть команд (включаю команду сохранения г), одна из которых - умножение.

9.4. БЕЗЗНАКОВОЕ ДЛИННОЕ ДЕЛЕНИЕ 153

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

Листинг 9.4. Длинное знаковое деление с использованием длинного беззнакового деления

int divls(int ul, unsigned uO, int v, int *r) {

int q, uneg, vneg, diff, borrow; uneg = ul » 31; -1, если u < 0. if (uneg)

( Вычисление абсолютного

uO = -uO; значения делимого u borrow = (uO != 0); ul = -ul - borrow;

vneg = V >> 31; -1, если v < 0.

v = (v * vneg) - vneg; Абсолютное значение v

if ((unsigned)ul >= (unsigned)v) goto overflow;

q = divlu(ul, uO, v, (unsigned *)r);

diff = uneg * vneg; Изменяем знак q, если

q = (q * diff) - diff; знаки u и v различны

if (uneg && r != NULL)

*r = -*r; if ((diff * q) < 0 q != 0)

{ При переполнении даем

overflow: остатку невозможное

if (г != NULL) значение и возвращаем

*г = 0x80000000; отрицательное частное

q = 0x80000000/ с максимально возможным

} абсолютным значением

return q;

В случае знакового деления достаточно трудно разработать действительно хороший код для обнаружения переполнения. Алгоритм, приведенный в листинге 9.4, выполняет предварителбйое обнаружение переполнения, идентичное случаю длинного беззнакового деления, которое гарантирует, что u/v < 2". После этого нам остается только убедиться,

что остаток имеет корректный знак или равен 0.