отличается от доказательства теоремы DC 1, только вместо первой формулы из теоремы D5 в доказательстве используется вторая.

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

Покажем, что (27) всегда имеет решение и что О < m < 2**.

Поскольку для любого неотрицательного числа х имеется степень 2, большая дг, но не превышающая 2jc + l, из (27) получаем

n,[d-\-rem(2 -<2" <2и,(f -1 -rem(2 -\,d)) + \. Так как QUTem[2-\d)<d-l,

\<2<2n,{d-\) + \. (28)

С учетом того, что n„d <.2" -I, это неравенство превращается в

1<2<2(2"-1)(2"-2) + 1

0<р<2И. (29)

Таким образом, неравенство (27) всегда имеет решение.

Если р не приравнивается принудительно к W, то из (25) и (28) следует

1,„ ,2яД-1) + 1л,+1

- S т<--,

2d-2 + l/n,,

1<т<---(«г +1),

l<m<2(n,+l)<2"*.

Если же р в принудительном порядке приравнено к W, то из (25) вытекает

2" 2"«.+1 - <т<----.

d d п

В силу того, что \<d<2-I и п,>2

iW-l

2W 22"-+1

-<т<

2<mS2"+l.

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

Доказательство корректности произведения в беззнаковом случае

Покажем, что если рят вычислены на основании формул (27) и (26), то выполняется уравнение (22).

Легко показать, что уравнение (26) и неравенство (27) приводят к первенству (25), которое практически тождественно неравенству (4); остальная часть доказательства, по сути, идентична доказательству для знакового деления при и а О.

struct mu magicu(unsigned d) {

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

unsigned nc, delta, ql, rl, q2, r2; struct mu magu;

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

nc = -1 - (-d)%d; Используется беззнаковая арифметика

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

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

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

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

r2 = 0X7FFFFFFF - q2*d; Инициализация r2=rem(2**p-l,d)

do {

P = P + 1; f (rl >= nc - rl)

ql = 2*ql + 1; rl = 2*rl - nC;

Коррекция ql Коррекция rl

ql = 2*ql; rl = 2*rl;

if (Г2 + 1 >= d - Г2)

else

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

r2 = 2*r2 + 1 - d; Коррекция г2

ГЛАВА 10 ЦЕЛОЕ ДЕЛЕНИЕ НА КОНСТАНТЫ

в реализации алгоритма, основанного на непосредственных вычислениях, использованных в доказательстве, имеются трудности. Хотя, как доказано выше, pu2W , случай p = 2W не исключается (например, для t/ = 2*-2, W>4). Если p=2W , вычислить т становится сложно в силу того, что делимое в (26) не размещается в 2W-6htobom слове.

Однако реализация этих действий возможна при использовании методики "инкре-ментного деления и взятия остатка", уже рассматривавшейся нами ранее и примененной для данного случая в алгоритме, который приведен в листинге 10.2 (для случая W=32). В этом алгоритме, помимо агического числа и величины сдвига, возвращается индикатор необходимости генерации команды add (в случае знакового деления необходимость добавления этой команды распознавалась по тому, что м и d имели разные знаки).

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

struct mu {

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

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

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

q2 = 2*q2;

r2 = 2*r2 + 1;

delta = d - 1 - r2; } while (p < 64 &&

(ql < delta (ql == delta && rl == 0))); magu.M = q2 + 1; Возвращаемые магическое число magu.s = p - 32; и величина сдвига return magu; (magu.a установлено ранее)

Приведем ряд ключевых моментов в понимании этого алгоритма.

• В ряде мест алгоритма может произойти беззнаковое переполнение, которое должно быть проигнорировано.

. =2" - rem(2",t/)-l = (2" -l)-rem(2 -d,d).

• Частное и остаток от деления 2 на не могут быть подкорректированы так же, как и в алгоритме из листинга 10.1, поскольку здесь величина 2*ri может вызвать переполнение. Следовательно, алгоритм должен выполнить проверку "if (ri>=nc-ri)" вместо более естественной проверки "if (2*ri>=nc)". Такое же замечание применимо и к вычислению часгаого и остатка от деления 2 -1 на.

• 0<Sid-\, так что представимо в виде 32-битового беззнакового целого числа.

• m = (2 + d-l-rem(2-l,d))/d=[(2-l)/dj + l = 9j + l.

• В программе не выполняется явное вычитание для случая, когда магическое число М превышает г" -1; это вычитание происходит в случае, когда вычисление q2 вызывает переполнение.

• Индикатор magu. а необходимости команды add из-за переполнения не может быть установлен путем непосредственного сравнения м с 2 или q2 с 2 -1. Вместо этого программа проверяет q2 до трго, как может произойти переполнение. Если q2 достигнет величины 2- -1, так что М станет не менее 2, то индикатору magu.a будет присвоено значение 1; в противном случае это значение останется равным 0.

• Неравенство (27) эквивалентно неравенству 2/п, > S.

• Проверка р < 64 в условии цикла необходима постольку, поскольку переполнение ql может привести к тому, что будет выполнено слишком большое количество итераций и будет получен неверный результат.

10.11. Дополнительные вопросы (беззнаковое деление)

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

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