Таким образом, если в таблице имеются делители 3, 5, 25, то могут быть обработаны делители 6, 10, 100 и т.д.

Такая процедура обычно дает наименьшее магическое число, хотя и не всегда. Если размер слова равен 32 бита, то наименьший положительный делитель, когда такое происходит, равен 334972. Данный метод при этом дает значения т=3361176179 и s=18; минимальное же магическое число для данного делителя составляет 840294045, а величина сдвига равна 16. Процедура также дает неминимальный результат при d = -6. В обоих приведенных случаях снижается качество генерируемого кода деления.

Алверсон [2] был первым, кто указал на корректность работы описываемого далее метода для всех делителей. Используя наши обозначения, можно сказать, что его метод для беззнакового целого деления на d состоит в использовании величины сдвига p = W+[logjt/] и множителя т= I/d с последующим выполнением деления

nd = mn/2 (т.е. путем умножения и сдвига вправо). Он доказал, что множитель т

меньше г** и что этот метод дает точное значение частного для всех п, выражаемых с помощью W-битового числа.

Метод Алверсона представляет собой более простой вариант нашего, в котором для определения р не используется поиск методом проб и ошибок, а следовательно, он в большей степени подходит для аппаратной реализации, в чем и состоит его главное назначение. Однако его множитель т всегда оказывается не меньшим, чем 2*, а потому при программной реализации всегда требуется код, проиллюстрированный в примере деления на 7 (т.е. всегда требуются либо команды add и shrxi, либо четыре альтернативные команды). Поскольку большинство небольших делителей могут быть обработаны при помощи множителей, меньших 2*, представляется разумным рассмотреть эти случаи.

В случае знакового деления Алверсон предложил искать множитель для \d\ и длины

слова W -1 (тогда г"" < m < 2* ), умножать на него делимое и, если операнды имеют противоположные знаки, изменять знак полученного результата. (Множитель должен быть таким, чтобы давать корректный результат для делимого г*", которое представляет собой абсолютное значение максимального отрицательного числа). Похоже, что такое предложение может дать код, лучший по сравнению с кодом для множителя таг*. Применяя данный прием к знаковому делению на 7, получим следующий код (где для того, чтобы избежать ветвления, использовано соотношение ~х = х + \):

abs an,n

li М,0x92492493 Магическое число (2**34+5)/7

mulhu q,M,an q = floor(M*an/2**32) shri q,q,2

shrsi t,n,31 Эти три команды

xor q,q,t изменяют знак q,

sub q,q,t если n отрицательно

Этот код не столь хорош, как тот, который был предложен для знакового деления на 7 ранее (7 и 6 команд соответственно), но он может оказаться полезным на компьютере, у которого есть команды abs и mulhu и нет команды mulhs.

10.13. ДРУГИЕ ПОХОЖИЕ МЕТОДЫ 185

Таблица 10.1. Некоторые магические числа для W = 32

Таблица 10.2. Некоторые магические числа для W = 64

10.15. Точное деление на константу

Под "точным делением" подразумевается деление, о котором заранее известно, что его остаток равен 0. Хотя такая ситуация и не очень распространена, она имеет место, например при вычитании двух указателей в языке С. В нем результат вычитания p-q, где рид - указатели, определен и переносим, только если рид указывают на объекты в

одном и том же массиве [32, раздел 7.6.2]. Если размер элемента массива равен s, то код для вычисления разности двух указателей реально вычисляет {p-q)/s.

Материал этого раздела основан на [21, ра:дел 9].

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

Теорема Ml. Если а и т - взаимно простые целые числа, то существует целое число 1<айт, такое, что аа sl(nMxlm).

Таким образом, а представляет собой обратный мультипликативный по модулю т элемент по отнощению к а. Есть несколько способов доказательства этой теоремы, три из них описаны в [49]. Доказательство, приведенное далее, требует только знания основ теории сравнений.

Доказательство. Докажем более общее по сравнению с данной теоремой утверждение. Если ант взаимно просты (и, следовательно, имеют ненулевые значения), то для множества jc, состоящего из т различных по модулю т значений, значения ах также будут различны по модулю т. Например, при а = 3 ит = 8 и значениях jc из диапазона от О до 7 получим, что значения ах представляют собой множество О, 3, 6, 9, 12, 15, 18, 21, или по модулю 8 это числа О, 3, 6, 1, 4, 7, 2, 5. Заметим, что в полученной последовательности вновь представлены все числа от О до 7.

Чтобы доказать это в общем случае, воспользуемся методом доказательства от противного. Предположим, что существуют два различных по модулю т целых числа, которые отображаются в одно и то же число по модулю т при умножении на а, т.е. существуют такие jc и у (л: * у (mod m)), что ах s ау (mod m). Но в таком случае существует целое

число к, такое, что

ах-ау = кт , или а{х-у) = кт.

Поскольку а не имеет общих множителей с т, разность х-у должна быть кратной т, т.е.

д:н y(mod m).

Однако этот вывод противоречит исходному предположению.

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

Приведенное доказательство показывает также, что имеется только одно значение jc (по модулю т), такое, что ax = l(madm), т.е. что мультипликативное обращение однозначно. Можно также показать, что имеется единственное (по модулю т) целое число jc, такое, что ах s Ь{пюй т), где Ь - любое целое число.

В качестве примера рассмотрим случай т = 16.Тогда 3 = 11,так как 311 = 33 = l(modl6). Можно также считать, что 3=-5, поскольку 3(-5) = -15 = l(nMdl6). Аналогично, -3 = 5, поскольку (-3) • 5 = -15 S l(mod 16).

Важность этих наблюдений заключается в том, что они показывают применимость рассматриваемых концепций как к знаковым, так и к беззнаковым числам. Если вы будете работать с беззнаковыми числами на 4-битовой машине, то получите 3 = 11; если же