Теорема DC3U. Для данного делителя d существует только один множитель т, имеющий минимальное значение р, если р не приравнивается kW в принудительном порядке.

Доказательства этих теорем практически идентичны доказательствам соответствующих теорем для знакового деления.

Делители с лучшими программами (беззнаковое деление)

Для того чтобы найти в случае беззнакового деления делители (если таковые имеются) с оптимальными программами поиска частного, состоящими из двух команд (li, mulhu), можно выполнить почти такой же анализ, как и для случая знакового деления (см. выше раздел "Делители с лучшими программами"). В результате анализа выясняется, что такими делителями являются делители чисел г" и 2* +1 (за исключением d = \). Для распространенных размеров слов таких нетривиальных делителей оказывается очень мало. При использовании 16-битовых слов таких делителей нет вовсе; для 32-битовых слов их всего два- 641 и 6700417. Два таких делителя (274177 и 67280421310721) есть и при работе с 64-битовыми словами.

Случай rf = 2*, * = 1,2,... заслуживает отдельного упоминания. В этом случае рассмотренный алгоритм дает нам p = W (принудительное присвоение) и m = 2"*. Это минимальное значение т, но не минимальное значение М. Наилучший код получается при использовании p = W + к. Тогда m = 2*, Af равно О, а - единице, s - к. Сгенерированный код включает умножение на О и может быть упрощен до одной команды сдвига вправо на величину к. На практике делители, представляющие собой степень 2, стоит рассматривать как особый случай и не привлекать для их обработки программу magicu. (Этого не происходит при знаковом делении, поскольку в этом случае т не может бьггь степенью 2. Доказательство. При d>0 неравенство (4), будучи скомбинированным с неравенством (3,6), дает d-\<2lm<d. Следовательно, 2jm не может быть целым числом. При rf <0 аналогичный результат получается при комбинировании неравенств (16) и (15,6).)

При беззнаковом делении, когда компьютер не имеет команды shrxi, код для случая таг* оказывается значительно хуже, чем код для т<2". Поэтому возникает вопрос, как часто приходится иметь дело с большими множителями. Для размера слова 32 бита среди целых чисел, меньших 100, имеется 31 "плохой" делитель: 1, 7, 14, 19, 21, 27, 28, 31, 35, 37, 38, 39,42,45, 53, 54, 55, 56, 57, 62, 63, 70, 73, 74, 76, 78, 84, 90, 91,95 и 97.

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

Если ваш компьютер не оснащен командой mulhu, но имеет команду mulhs (или команду знакового длинного умножения), то можно воспользоваться приемом, о котором говорилось в разделе 8.3.

В разделе 8.3 была приведена последовательность из семи команд, которая позволяет получить результат выполнения команды mulhu из команды mulhs. Однако в нашей ситуации этот прием упрощается, поскольку магическое число М известно заранее, так что компилятор может протестировать старший бит заранее и сгенерировать в соответствии с его значением ту или иную последовательность действий после выполнения команды "mulhu q, М,п". Здесь t обозначает временный регистр.

Мз1 =0 Мз1 = 1

mulhs q,M,n mulhs q,M,n

shrsi t,n,31 shrsi t,-n,31

and t ,.t. M and t, t, M

add q,q,t add t,t,n

add q,q,t

С учетом других команд, используемых вместе с mulhu, всего для получения частного и остатка от беззнакового деления на константу на компьютере, не оснащенном беззнаковым умножением, требуется от шести до восьми команд.

Этот прием можно обратить для получения команды mulhs из команды mulhu. При этом получается практически такой же код, только команда mulhs заменяется командой mulhu, а последние команды add в обоих столбцах заменяются командами sub.

Более простой беззнаковый алгоритм

Отказ от требования минимальности магического числа приводит к более простому алгоритму. Вместо (27) можно использовать

2>2"(t/-l-rem(2-l,t/)), (30)

а затем вычислить т, как и ранее, по формуле (26).

Должно быть очевидно, что формально этот алгоритм корректен (т.е. вычисленное значение т удовлетворяет уравнению (22)), поскольку единственное его отличие от предыдущего алгоритма состоит в том, что он вычисляет значение р, которое для некоторых значений d не обязательно будет большим. Можно доказать, что значение т, вычисленное по (30) и (26), меньше 2"*. Здесь доказательство опускается и просто приводится конечный результат - алгоритм, представленный в листинге 10.3.

Листинг 10.3. Упрощенный алгоритм вычисления магического числа для беззнакового деления

struct mu {

unsigned М; Магическое число int а; Индикатор "add"

int s; Величина сдвига

struct mu magicu2(unsigned d)

d должно быть в границах 1 <= d <= 2**32-1 int p;

unsigned p32, q, r, delta; struct mu magu;

magu.a =0; Инициализация индикатора "add"

p = 31; Инициализация p

q = 0x7FFFFFFF/d; Инициализация q = (2**p-l)/d

r = OxVFFFFFFF - q*d; Инициализация r = rem(2**p-l,d) do {

p = p + 1;

if (p == 32) p32 = 1; p32 = 2**(p-32). else p32 = 2*p32; if (r + 1 >= d - r)

10.11. ДОПОЛНИТЕЛЬНЫЕ ВОПРОСЫ (БЕЗЗНАКОВОЕ ДЕЛЕНИЕ) 183

if (q >= 0X7FFFFFFF) magu.a = 1; q = 2*q +1; Коррекция q

r = 2*r + 1 - d; Крррекция r

else {

if (q >= 0x80000000) magu.a = 1;

q = 2*q;

r = 2*r + 1;

delta = d - 1 - r; } while (p < 64 && p32 < delta);

magu.M = q + 1; Возвращаемые магическое число

magu.s = p - 3 2; и величина сдвига

return magu; (magu.a установлено ранее)

Алверсон [2] предложил более простой алгоритм, который рассматривается в следующем разделе, но он иногда дает очень большие значения т. Главное в алгоритме magicu2 В том, что он почти всегда дает минимальное значение т при d<2\ Если размер слова равен 32 битам, наименьший делитель, для которого magicu2 не дает минимального множителя, равен 102807 (в этом случае magicu дает значение т, равное 2 737 896 999, а magi cu2 - значение 5 475 793 997).

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

10.12. Применение к модульному делению и делению с округлением к меньшему значению

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

10.13. Другие похожие методы

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

1) Подсчитывается количество завершающих нулевых битов в d, которое далее обозначается как к.

2) В качестве аргумента поиска в таблице используется значение d/2 (сдвиг вправо на к позиций).

3) Используем магическое число, найденное в таблице.

4) Используем найденную в таблице величину сдвига, увеличенную на к.