в этом случае нам требуется команда mulhu, которая возвращает старшие 32 бита беззнакового 64-битового произведения.

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

2» + 1 п

3 2

3 3-2»

При 0<п<2- выполняется неравенство 05пДз-2")<1/3, так что в соответствии с теоремой D4 = [n/3j.

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

Беззнаковое деление на 7

При беззнаковом делении на 7 на 32-битовом компьютере множители (2" + 3)/7, (2"+ 6)/? и (2*+5)/? оказываются неадекватными, поскольку дают слишком большой член-ошибку. Можно использовать множитель (2"+з)/7, но он слишком велик для представления 32-битовым беззнаковым числом. Умножение на это число можно выполнить посредством умножения на (2 + 3)/7-2" с последующей коррекцией путем сложения. Соответствующий код имеет следующий вид:

li N,0x24924925 Магическое число (2**35+3)/7 - 2**32

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

add q,q,n Может вызвать переполнение (перенос)

shrxi q,q,3 Сдвиг вправо с битом переноса

muli t,q,7 Вычисление остатка по формуле

sub r,n,t г = n q*7

Здесь возникает небольшая проблема: команда add может вызвать переполнение. Для того чтобы обойти эту ситуацию, была придумана новая команда расширенного сдвига вправо на непосредственно заданную величину (shrxi), которая рассматривает бит переноса команды add и 32 бита регистра д как единую 33-битовую величину, и выполняет ее сдвиг вправо с заполнением освободившихся разрядов нулевыми битами. В семействе процессоров Motorola 68(ХЮ эти действия можно реализовать при помощи двух команд: расширенного циклического сдвига вправо на один бит с последующим беззнаковым сдвигом вправо на 3 бита (команда гогх на самом деле использует Х-бит, но команда add присваивает ему то же значение, что и биту переноса). На большинстве компьютеров для выполнения этих действий требуется большее количество команд. Например, на PowerPC требуется выполнение трех команд: сброс правых трех битов д, прибавление бита переноса к g и циклический сдвиг вправо на три позиции.

При той или иной реализации команды shrxi приведенный выше код вычисляет

2"+Ъ

п Ъп -+-

L3 7-2«J

При О < и < 2- выполняется неравенство, О < ЗиД7 • 2") < 1/7 , так что в соответствии с теоремой D4 9 = [n/7j •

Гранлунд (Granlund) и Монтгомер1 (Montgomery) [21] предложили остроумную схему, позволяющую избежать применения команды shrxi. Она требует того же количества команд, что и рассмотренная выше схема, но использует только элементарные команды, которые есть практически у каждого компьютера; переполнения при этом оказываются просто невозможны. Схема использует следующее тождество:

д + п 2"

, р>1.

Применим данное тождество к нашей задаче, полагая д= Мп/2 , где 0<М<2. Вычитание не может вызвать переполнения, поскольку

п~д=п-

J L

2".

поэтому очевидно, что О < и - < 2-. Сложение также не может вызвать переполнения, поскольку

п-д 2

+ д =

п + д 2

и 0<.п,д<2-.

Использование предложенных идей приводит к следующему коду для беззнакового деления на 7:

li N,0x24924925 Магическое число (2**35+3)/7 - 2**32

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

sub t,n,q t=n-q

shri t,t,l t = (n - q)/2

add t,t,q t = (n - q)/2 + q = (n + q)/2

shri q,t,2 q = (n+Mn/2**32)/8 = floor(n/7)

muli t,q,7 sub r,n,t

Вычисление остатка по формуле г = n - q*7

Чтобы эта схема работала, величина сдвига в гипотетической команде shrxi должна быть больше 0. Можно показать, что если </ > 1 и множитель т > 2" (т.е. необходима команда shrxi), то величина сдвига больше 0.

10.9. Беззнаковое деление на делитель, не меньший 1

Для данного размера слова W> 1 и делителя l<d<2 требуется найти наименьшее целое т и целое р, такие, что

(22)

для 0Sn<2",

при этом 0Sm<2** и ргУ/ .

В случае беззнакового деления магическое число М определяется как

0Sm<2",

Xm-l". 2»<т<2"Л

Поскольку(22) должно выполняться для и=d, md/l =1 или

Пусть, как и в случае знакового деления, Пс представляет собой наибольшее значение п, такое, что гет(п,</) = </-!. Его можно вычислить иж п,= t/-l = 2"-rem(2",t/)-l.

Тогда

2*-t/S«,S2»-l

Это означает, что > 2.

Поскольку (22) должно выполняться при и = и,,

n,-(d-l)

(24,а) (24,6)

тп, и, +1

2" d

Объединение этого неравенства с (23) дает

2 2 п,+\

- <т<---

d d п.

(25)

Поскольку т представляет собой наименьшее целое, удовлетворяющее неравенству (25), оно должно быть ближайшим целым числом, большим или равным 2ld , т.е.

2 + d-\-Km[2-\,d]

Комбинируя это уравнение с правой частью (25) и упрощая, получим

2>n,(t/-l-rem(2-l,t/))

(26)

(27)

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

Таким образом, алгоритм состоит в поиске методом проб и ошибок минимального ps.W , удовлетворяющего неравенству (27), после чего из уравнения (26) вычисляется т. Это наименьшее возможное значение т, удовлетворяющее (22) при p>W . Как и в знаковом случае, если неравенство (27) выполняется для некоторого значения р, то оно выполняется и для всех больших значений р. Доказательство этого факта, по сути, ничем не