ГЛАВА 10

ЦЕЛОЕ ДЕЛЕНИЕ НА КОНСТАНТЫ

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

10.1. Знаковое деление на известную степень 2

Многие ошибочно считают, что знаковый сдвиг вправо на к позиций делит число на 2* с использованием обычного отекающего деления [20]. Однако на самом деле не все так просто. Приведенный ниже код выполняет деление = я+2*, где 1S it S 31 [29].

shrsi t,n,k-l Формируем целое число

shri t,t,32-k 2**к - 1, если п < 0; иначе О

add t,n,t Добавляем его к п

shrsi q,t,k и выполняем знаковый сдвиг

вправо

Этот код не содержит команд ветвления. Он может быть упрощен до трех команд при делении на 2 (А:= 1). Однако данный код имеет смысл только на компьютерах, которые способны выполнить сдвиг на большое значение за малое время. Случай к=Ъ1 не имеет особого смысла, поскольку число 2 не представимо на компьютере. Тем не менее приведенный код дает правильный результат и в этом случае ( = -1, если и = -2", и ? = 0 для прочих значений п).

Для деления на -2* после приведенного выше кода должна следовать команда изменения знака. Лучшего варианта для данного деления пока не придумано.

Вот еще один, более очевидный и простой код для деления на 2*:

bge п,label Ветвление при п >= О

addi n,n,2**k-l Прибавление 2**к - 1 к п label shrsi n,n,k и знаковый сдвиг вправо

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

Компьютер PowerPC имеет необычное устройство для ускорения деления на степень 2 [16]. Команда знакового сдвига вправо устанавливает бит переноса, если сдвигаемое число отрицательно и был сдвиг одного или нескольких единичных битов. Кроме того, данный компьютер имеет команду addze для сложения бцта переноса с регистром. Все это позволяет реализовать деление на любую (положительную) степень 2 с помощью двух команд;

shrsi q,n,k addze q,q

Единственная команда сдвига shrsi на к позиций выполняет знаковое деление на 2*, которое совпадает как с модульньпл делением, так и с делением с округлением к мень-

шему значению. Это наводит на мысль о том, что такое деление может быть предпочтительнее для использования в языках высокого уровня, чем деление с отсечением, так как позволяет компилятору для деления на 2 использовать единственн>то команду shrsi. Кроме того, команда shrsi с последующей за ней командой neg выполняет модульное деление на -2*, что, в свою очередь, указывает на преимущества использования модульного деления (впрочем, в основном это вопрос эстетического восприятия, в силу того что задача деления на отрицательную константу встречается достаточно редко).

10.2. Знаковый остаток от деления на степень 2

Если нам требуется вычислить и частное и остаток от деления л + 2*, простейщий путь получения значения остатка - вычислить его по формуле г = 9* 2* - я, для чего после вычисления частного требуется выполнение двух команд:

shli r,q,k sub г,г,n

Для вычисления одного лищь остатка необходимо выполнить около четырех или пяти команд. Один из способов вычисления состоит в использовании рассмотренной ранее последовательности из четырех команд для знакового деления на 2*, за которой следуют две команды вычисления остатка. При этом две последовательные команды сдвига можно заменить командой и, что дает нам решение из пяти команд (четырех при fc= 1).

shrsi t,n,k-l Формируем целое число

shri t,t,32-k 2**к - 1, если п < 0; иначе О

add t,n,t Добавляем его к п,

andi t,t,-2**k сбрасываем к правых битов

sub r,n,t и вычитаем его из п

Еще один метод основан на том, что

гет(п,2)= ,Л , /,

I -((-„)&(2-1)), „<0.

Для того чтобы воспользоваться этой формулой, сначала вычисляем / <- ns>31, а затем

r<-((abs(n)&(2-l))©/)-( (требуется пять команд) или в случае к= 1, так как (-я) & 1 = я & 1, вычисляем

г<-((я&1)Ф()-<

(требуется четыре команды). Этот метод не очень хорош при к>1, если компьютер не оснащен командой вычисления абсолютного значения (в таком случае вычисление ос-taTKa будет требовать выполнения семи команд). Еще один меТод основан на том, что

(«,2) =

п&(2*-1), п20,

((п + 2*-1)&(2-1))-(2-1), п<0.

Эта формула приводит к вычислениям

т <-

&

(при к> 1 требуется выполнение пяти команд, при к-= \ - четырех). Все перечисленные методы работают при \ <к<,Ъ\.

Кстати, если в компьютере нет команды знакового сдвига вправо, то значение, которое равно 2* -1 для и < О и О для и й О, может быть построено следующим образом:

r«-(f,«fc)-f„

что приводит к дооавлению только одной команды.

10.3. Знаковое деление и вычисление остатка для других случаев

Основной прием в этом случае состоит в умножении на некоторое соответствующее делителю d число, примерно равное 27t/, с последующим выделением 32 левых битов произведения. Однако реальные вычисления для ряда делителей, в частности для 7, оказываются существенно сложнее.

Рассмотрим сначала несколько конкретных примеров» которые пояснят код, генерируемый обобщенным методом. Обозначим регистры следующим образом:

п - входное целое число (числитель); м - в него загружается "магическое число"; > t - временный регистр; q - в нем будет размещено частное; г - в нем будет размещен остаток.

Деление на 3

li М,0x55555556

mulhs q,M,n

shri t,n,31

add q,q,t

muli t,q,3 sub r,n,t

Загрузка "магического числа" (2**32+2)/3 q = floor(M*n/2**32) Прибавляем 1 к q, если n отрицательно

Вычисляем остаток как г = п - q*3

Доказательство. Операция старшее слово знакового умножения не может вызвать переполнения, поскольку произведение двух 32-битовых чисел всегда может быть представлено 64-битовым числом, а команда mulhs возвращает старщие 32 бита 64-битового

произведения. Это действие эквивалентно делению 64-битового произведения на 2 и вычислению функции floor() от полученного результата, причем это замечание справедливо независимо от того, отрицательно рассматриваемое произведение или положительно. Таким образом, при и > О приведенный выше код вычисляет

2"+ 2 и

3 2-

и In 33-2

10.3. ЗНАКОВОЕ ДЕЛЕНИЕ И ВЫЧИСтеНИЕ ОСТАТКА ДЛЯ ДРУГИХ СЛУЧАЕВ