манды, например команду HP PA-RISC сдвиг и сложение (она сдвигает содержимое регистра на одну, две или три позиции, складывает с содержимым второго регистра и помещает результат в третий регистр; таким образом можно осуществить умножение на 3, 5 или 9 одной, по-видимому, очень быстрой командой). Будем также считать, что нас интересуют только младшие 32 бита произведения.

Первое улучшение к предложенной выше базовой схеме бинарного разложения состоит в использовании вычитания для сокращения последовательности вычислений, если множитель содержит группу из трех или большего количества последовательных единичных битов. Например, для умножения на 28 (11100 в двоичном представлении) можно вычислить 32х~Ах (три команды) вместо того, чтобы вычислять 16х + &х+4х запять команд. На машинах с использованием дополнения до двойки конечный результат остается корректным, даже если промежуточное значение 32* вызывает переполнение.

Умножение на константу т по схеме бинарного разложещш с использованием только команд сдвига и сложения требует выполнения 2pop(m)-l-J команд, где 3 = 1, если т

завершается единичным битом (нечетно), и равно О в противном случае. Если же в дополнение к перечисленным командам используются команды вычитания, то умножение требует вьшолнения 4g(m) + 2s(m)-l-<5 команд, где g(m) -количество групп из двух и

более последовательных единичных битов в /я, а s(m) - количество "одиноких" единичных битов. Значение Sопределяется так же, как и ранее. Для группы из двух байтов оба метода равноценны.

Следующее улучшение состоит в рассмотрении групп специализированного вида, состоящих из разделенных одним нулевым битом грутш из последовательных единичных битов. Рассмотрим, например, т=55 (110111 в двоичном представлении). Метод групп позволяет вычислить произведение путем выполнения шести команд: {64х -16х)+{&х - х). Если же

вычислять произведение как Мх~&х-х, то потребуется выполнение только четырех команд. Аналогично, умножение на двоичное число 110111011 требует выполнения шести команд, что иллюстрируется формулой 512* - 64* - 4* - * .

Приведенные выше формулы дают верхнюю границу количества команд, требующихся для умножения переменной х на данное число т. Другая граница может быть получена исходя из размера т в битах: и = [log m j +1.

Теорема. Умножение переменной х на п-битоеую константу т, т>1, может быть выполнено не более чем за п команд сложения, вычитания и сдвига влево на некоторое заданное значение.

Доказательство (по индукции по и). Умножение на 1 выполняется за О команд, так что для п=1 теорема справедлива. Для п>1 умножение на /и (если т заканчивается нулевым битом) можно реализовать путем умножения на число, представляющее собой левые и -1 битов числа т (т.е. на т/2) за п-1 команду, и сдвига влево на одну позицию,

т.е. всего за и команд.

Если т в двоичном исчислении заканчивается на 01, то тх можно вычислить путем умножения X на число, состоящее из левых и - 2 битов т (для чего потребуется не более и-2 команд), с последующим сдвигом результата влево на две позиции и сложения с х. Всего для этого требуется выполнение п команд.

Если т в двоичном исчислении заканчивается на 11, то нужно рассмотреть случаи, когда т в двоичном представлении заканчивается "на ООН, 0111, 1011 и 1111. Пусть

/- результат умножения х на левые и-4 бита т. Если т заканчивается на ООП, то тх = Ш + 2х + х , для чего требуется выполнение (п-4) + 4 = п команд. Если т заканчивается на 0111, то mx = l6t+Sx~x ,а если на 1111 - то тх = Ш+ 1бх ~х;ъ обоих случаях для вычислений требуется выполнить и команд. Последний случай - когда двоичное представление т заканчивается на 1011.

При этом легко показать, что тх можно вычислить за п команд, если т заканчивается на 001011, 011011 или 111011. Остается рассмотреть случай 101011.

Эти рассуждения можно продолжать - и всякий раз "последний случай" будет представлять собой число вида 101010...10101011. В конце концов будет достигнут размер т и нам останется рассмотреть только п-битовое число 101010...10101011, которое содержит n/2+l единичных битов. Но ранее было показано, что х на такое число можно умножить за 2(п/2 + 1)-2 = п команд.

Таким образом, на 32-битовом компьютере, например, умножение на любую константу может быть выполнено максимум за 32 команды в соответствии с описанным выше методом.

Проверка показывает, что, когда п четно, п-битовое число 101010...101011 требует выполнения п команд, как и число 1010101. ..010110 в случае нечетного ц, так что указанная граница компактна.

Описанная методология не слишком сложна до тех пор, пока мы работаем с ней вручную или встраиваем в алгоритм для использования, например, в компиляторе. Однако такой алгоритм не всегда дает оптимальный код, поскольку иногда возможно дальнейшее его улучшение. Это улучшение может использовать, например, результаты разложения т или промежуточные результаты вычислений. Взглянем еще раз на случай т=45. Описанный выше метод требует выполнения шести команд, но разложение 45 на множители 5 и 9 дает нам решение с использованием всего четырех команд.

t*-Ax + x

Разложение может быть скомбинировано с аддитивными методами. Например, умножение на 106 при использовании аддитивного метода требует выполнения семи команд, но запись 106 как 7 15 + 1 дает решение, состоящее из пяти команд.

Решение задачи о максимальном количестве команд, необходимом для умножения на «-битовую константу с использованием разложения, автору не известно. Для больших и оно может быть меньше, чем доказанная ранее граница п. Например, значение ffi=OxAAAAAAAB без использования разложения требует 32 команд, но если записать это значение как 2-5 17-257-65537+1, то будет получено решение, состоящее из 10 команд (что, вероятао, нетипично для больших чисел; разложение отражает чередование единичных и нулевых битов в двоичном представлении числа).

В [39, раздел 4.6.3] рассматривается тесно связанная с данной задачей проблема вычисления а" с использованием минимального количества умножений. Эта задача аналогична задаче умножения на m с использованием только команд сложения. Алгоритм вычисления тх, который можно использовать в компиляторе, описан в [5].

ГЛАВА 9

ЦЕЛОЧИСЛЕННОЕ ДЕЛЕНИЕ

9.1. Предварительные сведения

в этой и следующей главах приводится ряд приемов и алгоритмов "компьютерного деления" целых чисел. В математических формулах используется запись х/у для обозначения обычного деления, х+у - для знакового компьютерного деления целых чисел

(с отсечением дробной части), и х+у - для беззнакового компьютерного деления целых чисел. В коде на языке С х/у означает компьютерное деление, которое может быть как знаковым, так и беззнаковым - в зависимости от его операндов.

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

Отсечение Модуль Округление

к меньшему значению

7-1-3 = 2 rem 1 2 rem 1 2 rem 1

(-7)-i-3 = -2 rem -1 -3 rem 2 -3 rem 2

7-i-(-3) = -2 rem 1 -2 rem 1 -3 rem -2

(-7)-b(-3) = 2 rem -1 3 rem 2 2 rem -1

Соотношение Делимое Частное* Делитель + Остаток выполняется при любом определении целочисленного деления. "Модульное" деление определяется как требующее, чтобы остаток от деления был неотрицательным, а деление с округлением к меньшему значению требует, чтобы результат представлял собой наибольшее целое число, не превосходящее результата рационального деления. При положительном делителе эти два метода дают одинаковые результаты. Есть и четвертый, редко используемый вариант целочисленного деления, когда результат рационального деления округляется до ближайшего целого числа.

Одно из достоинств модульного деления и деления с округлением к меньшему значению заключается в том, что они упрощают ряд используемых приемов. Например, деление на 2" можно заменить знаковым сдвигом вправо на п позиций, а остаток от деления jc на 2" получается в результате применения операции м к jc и 2" -1. Я также подозреваю, что модульное деление и деление с округлением к меньшему значению чаще дают тот результат, который вас интересует. Например, предположим, что вы пишете программу

Я знаю, что меня будут критиковать за такую классификацию,, поскольку из понятия "модуль" не следует понятие "неотрицательный". Оператор mod у Кнута [38] означает остаток от деления с округлением к меньшему значению (floor), который имеет отрицательное значение (или равен 0), если делитель отрицателен. Ряд языков программирования определяет функцию mod как остаток при отсекающем делении. Однако, например, в теории комплексных чисел модуль есть величина неотрицательная, как и в ряде других разделов математики.