q = q + 1;

r = r - abs(d);

Из левой половины неравенства (4) и правой половины (16) вместе с доказанным границами для т следует, что =1 г""/!*?!] < 2* , так что q можно представить W-6HT0Bbii

беззнаковым числом. Кроме того, О S г < , так что г можно представить W-6htobi>ii

знаковым или беззнаковым числом. (Внимание: промежуточный результат 2г може. превысить 2* -1, поэтому г должно быть беззнаковым числом, и выполняющиеся выш( сравнения также должны быть беззнаковыми.)

Далее вычисляется J = - г. Оба члена разности представимы в виде -битовш

беззнаковых целых чисел (так же, как и разность 1S J < ), так что данное вычислени

не представляет никаких трудностей.

Для того чтобы избежать длинного умножения в (19), перепищем его в виде

Величина 2/\п,\ представима в виде W-битового беззнакового целого числа (анало

гично (7), из (19) может быть показано, что 2*" S2nd и если rf=-2", то и, =-2*+1

и р = 2М-2, так что 2/п, = 2*У(2*~-1)<2* при йЗ). Эти вычисления так же, как

и в случае rem(2,jt/), могуг быть инкремеитными (при увеличении р). Сравнение для

случая 2/п2 2*" (что может произойти при больших <f) должно быть беззнаковым.

Для вычисления т не требуется непосредственное вычисление (20), при котором может понадобиться длинное деление. Заметим, что

2[t/[-rem(2[t/[) 2

м т

Проверка завершения цикла 2/\п,\ > 5 вычисляется достаточно сложно. Величина 2f\n\

доступна только в виде частного qx и остатка г\. Величина 2j\n\ может бьпъ (а может и не

быть) целой (эта величина является целой только для d - 2* +1 и некоторых отрицательных значений йО-Проверка 2f\n\<.S может быть закодирована следующим образом:

<,,<81(<,,=8&г,=0).

Полностью процедура для вычисления м и s для данного d показана в листинге 10.1, где представлена программа на языке С для IV = 32 . Здесь есть несколько мест, где может произойти переполнение, однако если его игнорировать, то полученный результат оказывается корректным.

Листинг 10.1. Вычисление магического числа для знакового деления

struct ms {

int М; Магическое число int S; Величина сдвига

+ \ = q + \.

struct ms magic(int d)

( d должно удовлетворять условию

2 <= d <= 2**31-1 или -2**31 <= d <= -2

int p;

unsigned ad, anc, delta, ql, rl, q2, r2, t; const unsigned two31 = 0x80000000; 2**31 struct ms mag; ad = abs(d);

t = twc31 + ((unsigned)d >> 31);

anc = t - 1 - t%ad; Абсолютное значение пс

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

ql = two31/anc; Инициализация ql = 2**p/nc

rl = two31 - ql*anc; Инициализация rl = rem(2**p,nc)

q2 = two31/ad; Инициализация q2 = 2**p/d

r2 = two31 - q2*ad; Инициализация г2 = rem(2**p,d)

do {

p = p + 1;

ql = 2*ql; Обновление ql = 2**p/nc.

rl = 2*rl; Обновление rl = rem(2**p,nc)

if (rl >= anc) Здесь требуется беззнаковое { сравнение

ql = ql + 1;

rl = rl - anc;

q2 = 2*q2; Обновление q2 = 2**p/d

r2 = 2*r2; Обновление г2 = rem(2**p,d)

if (r2 >= ad) Здесь требуется беззнаковое { сравнение

q2 = q2 + 1;

Г2 = Г2 - ad;

delta •= ad - г2; } while (ql < delta (ql -= delta && rl == 0)); mag.M = q2 + 1; if (d < 0)

mag.M = -mag.M; Магическое число и mag.s = p - 32; величина сдвига

return mag;

Для использования результата этой программы компилятор должен сгенерировать команды Ни mulhs, команду add при d > о и м < о или sub при d<OHM>OH, наконец, команду shrsi при s > 0. После этого генерируются команды shri и add.

В случае W = 32 можно избежать обработки отрицательного делителя, если использовать предвычисленный результат для d=3 и =715827883, а для остальных отрицательных делителей использовать формулу m{-d) = -m(d). Однако при этом программа

из листинга 10.1 не станет значительно короче (если вообще сократится).

10.7. Дополнительные вопросы

Теорема DC2. Наименьший множитель т нечетен, если р не равно W в принудительном порядке.

Доказательство. Предположим, что уравнения (1,а) и (1,6) выполняются при наименьшем (не установленном принудительно) значении р и четном т. Очевидйо, что тогда т можно разделить на 2, а р уменьшить на 1 и уравнения останутся справедливы. Но это противоречит предположению о том, что р- наименьшее значение, при котором выполняются данные уравнения.

Единственность

Магическое число для данного делителя может быть единственным (как, например, в случае W=32, d=l), но зачастую это не так. Более того, эксперименты указывают, что как раз обычно имеется несколько магических чисел для одного делителя. Например, для W=32, d=e имеется четыре магических числа:

Л/= 715827833 ((2" + 2)/б) s = 0

М= 1431655766 ((2"+2)/з) s=l

М= -1431655765 ((2" + 1)/3-2=) s = 2

М= -1431655764 ((2" + 4)/3-2) s = 2. Однако есть следующая теорема.

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

Доказательство. Рассмотрим сначала случай d>0. Разность между верхней и нижней границами в неравенстве (4) составляет 2/dn,. Мы уже доказали (7), т.е. что если р минимально, то 2/dn, < 2. Таким образом, может быть не более двух значений т, которые удовлетворяют неравенству (4). Пусть т равно минимальному из этих значений, задаваемому соотношением (5); тогда второе допустимое значение - га +1.

Пусть Ро - наименьшее значение р, для которого т +1 удовлетворяет правой части неравенства (4) (значениеро не приравнено к Wb принудительном порядке). Тогда

2"+rf-rem(2.rf) 2 я,+1 d d п,

Это выражение упрощается до >

г" >n2d-rem(2*,d)).

Деление на 2 дает

/ J N

2->и, d-rem(2°.d) . V 2 J

Поскольку в соответствии с теоремой D5 из раздела 9.1 rem(2,rf)< 2rem(2",d), получаем

2"->n,(rf-rem(2°",d)),

что противоречит предположению о минимальности ро-

Доказательство для случая d<0 аналогично и здесь не приводится.