битовых переменных. Кроме того, в программе выполняется m-n + l команд деления и одна - вычисления количества ведущих нулевых битов.

Знаковое деление больших чисел

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

1. Изменить знак у делимого, если оно отрицательно. Сделать то же для делителя.

2. Преобразовать делимое и делитель в беззнаковое представление.

3. Использовать алгоритм беззнакового деления больших чисел.

4. Преобразовать частное и остаток в знаковое представление.

5. Изменить знак частного, если знаки делимого и делителя были различны.

6. Если делимое отрицательно, изменить знак остатка.

Иногда вьшолнение этих шагов требует добавления или удаления старшего бита. Нагфи-мер, предположим для простоты, что числа представлены в системе счисления с основанием 256 (один байт на цифру) и что при знаковом представлении числа старший бит последовательности цифр является знаковым. Такое представление наиболее похоже на обычное представление чисел в дополнительном коде. В этом случае делитель 255, который в знаковом представлении имеет вид Ох(ЮРР, при выполнении шага 2 должен быть сокращен до OxFF. Аналогично, если частное из шага 3 начинается с единичного бита, для корректного представления в виде знакового числа нужно добавить к нему ведущий нулевой байт.

9.3. Беззнаковое короткое деление на основе знакового

Под "коротким делением" подразумевается деление одного слова на другое (т.е. деление типа 32+32 => 32). Это обычное деление, которое в языке С и многих других языках программирования высокого уровня выполняется оператором "/" с целыми операндами. В С имеется и знаковое и беззнаковое короткое деление, но в ряде компьютеров в набор команд входит только знаковое деление. Каким образом можно реализовать беззнаковое деление на такой машине? Непохоже, чтобы такая задача решалась гладко и просто, тем не менее рассмотрим некоторые возможные варианты.

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

Даже если компьютер оснащен знаковым длинным делением (64 + 32 => 32), осуществление беззнакового короткого деления не такая простая задача, как может показаться на

реализуется следую-

первый взгляд. В компиляторе XLC для IBM RS/6000 q<r- n+d щим образом (запись с использованием псевдокода).

1. if n<d then qO

2. else if rf=l then q*-n

3. else if rfl then

4. else 9<-(0n)+rf

Третья строка в действительности проверяет выполнение условия rfa2. Если d в этом месте атбраически меньше или равно 1, то, поскольку оно не равно 1 (эта проверка выполнялась во второй строке), алгебраически оно доласно не превышать 0. Нас не беспокоит случай d=Q, поэтому, если проверяемое в третьей строке условие истинно, это

означает, что установлен знаковый 6tkd, т.е. rf>2" . Посколькуиз первой строки известно, что п></, и л не может превышать 2" -1, то = 1.

Запись в четвертой строке означает формирование целого числа двойной длины, состоящего из 32 нулевых битов, за которыми следует 32-битовая величина и, и деление его на d. Проверка d=l во второй строке необходима для того, чтобы гарантировать, что

это деление не вызовет переполнения (переполнение может возникнуть при я>2, и частное в этом случае оказывается неопределенным).

Если объединить сравнения во второй и третьей строках, то описанный выше алгоритм может быть реализован при помощи 11 команд, три из которых - команды ветвления. Если необходимо выполнение деления при rf=0 (завершающееся генерацией прерывания), то третью строку можно заменить строкой "else if rf<0 then что приводит к 12-командной реализации на машине RS/6000.

Не так сложно изменить код таким образом, чтобы наиболее вероятные значения

(2<rf<2 ) не требовали такого большого количества проверок (начав код с проверки if rf < 1), но это приведет к некоторому увеличению объема получаемого кода.

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

Если знаковое длинное деление недоступно, но есть знаковое короткое деление, то n+d можно реализовать приведением задачи к случаю n,d<2 и использованием машинной команды деления. Если rfa2*, то я+rf может быть только О или 1, так что от этого условия легко освободиться. Далее можно воспользоваться тем фактом, чо выра-

жение я+2 +rf х2 приближенно равно значению я+rf с ошибкой, равной О или 1.

\.\ J J

Это приводит нас к следующему методу (записан с использованием псевдокода).

1. if d<0 then if я<rf then qO

2. else

3. else do

я+2j+rfjx2

5. r<n-qd

6. if r>rf then q<:-q + l

7. end

Выполнение команды сравнения на RS/6000 устанавливает биты состояния, указывающие выполнение отношений меньше, больше и равно.

9.3. БЕЗЗНАКОВОЕ КОРОТКОЕ ДЕЛЕНИЕ НА ОСНОВЕ ЗНАКОВОГО 147

npoBq№a <0 в первой строке на самом деле выясняет, не выполняется ли условие </ 2 2*. Если это условие истинно, то наибольшее частное может бьггь рашо только (2 -1) »• 2 = 1,

так что первые две строки 1федставлякгг собой вычисление частного для случая rf 22" .

Четвертая строка представляет собой код, выполняюший команды беззнакового сдвига вправо на 1 бит, деления, сдвига влево на 1 бит. Понятно, что я-!-2<2" , и к этому моменту мы убедились, что и rf<2, а потому эти величины могуг использоваться в машинной команде знакового деления (если d=p, машина сообщит о переполнении). Вычисления в четвертой строке дают следующую оценку частного (с использованием следствия из теоремы D3):

В строке 5 вычисляется соответствующий этому частному остаток:

n-rem(n.2d) ,

г = „--i-d = rem(n,2rf).

Таким образом, О < г < 2d . Если r<d, то q представляет собой корректный остаток. Если же rd, то верное значение частного получается добавлением 1 к вычисленному в строке 4 значению (при выполнении проверки значения остатка программа должна использовать беззнаковое сравнение, так как возможна ситуация, когда г > 2).

Загружая значение О в 9 до выполнения сравнения n<rf и кодируя присвоение в строке 2 как переход к присвоению д*-д + 1 в строке 6, получим 14 команд на большинстве машин, четыре из которых будут представлять собой команды ветвления. Достаточно просто дополнить данный код для вычисления не только частного, но и остатка от деления. Дня этого необходимо добавить к строке 1 присвоение г <- я , к строке 2 - г <-п -rf , а к части "then" строки б - г <-г -rf (либо, если пойти на использование команды умножения, можно обойтись единственным добавлением присвоения rn-qd после выполнения всех вычислений).

Альтернативой строкам 1 и 2 являются строки

if n<d then «-0

else if rf<0 then q-l,

что приводит к более компактному коду, состоящему из 13 команд, три из которых являются командами ветвления. Однако в этом случае для наиболее вероятной ситуации (небольшие величины, n>d) будет выполняться большее количество команд.

Используя выражения предикатов, программу можно пфеписать следующим образом.

1. if rf<0 then q*r-

2. else do

[nkd)

3. 9.

n*2Ud x2

\X J J

4. r*-n-qd