+ 1 при и>0.

Однако добавление 1 при положительных значениях п неудобно (так как невозможно просто использовать знаковый бит п), так что вместо этого будет выполняться прибавление 1, если значение q отрицательнр. Эти действия эквивалентны, поскольку сомножитель т отрицателен (как будет показано далее).

Генерируемый для случая W-32, d = -l код показан ниже.

Этот код очень напоминает код для деления на +7, с тем отличием, что он использует множитель для деления на +7, но с обратным знаком, команду вычитания вместо команды умножения, а кроме того, команда сдвига shri использует д, а не и (о чем говорилось ранее). (Заметим, что в случае деления на +7 также можно использовать в качестве операнда q, но при этом код будет иметь меньшую степень параллелизма.) Команда вычитания не может привести к переполнению, поскольку операнды имеют один и тот же знак.

Тем не менее эта схема работает не всегда. Хотя приведенный код для W = 32, </ = -7 вполне корректен, аналогичные изменения кода деления на 3 для получения кода для деления на -3 приведут к неверному результату при W = 32, и = -2".

Рассмотрим ситуацию подробнее.

Пусть дан размер слова W >3 и делитель -2"" <d<-2 и требуется найти наименьшее (по абсолютному значению) целое -2" йтйО и целбе p>W , такие, что

2"

+1 =

для -2-<п<0,

для 1<и<2*

(14,а)

(14,6)

Поступим так же, как и в случае деления на положительный делитель. Пусть п - наибольшее по абсолютной величине отрицательное значение п, такое, что и, = Ы +1 для

некоторого целого к. Такая величина Пс сушествует в силу того, что имеется по крайней мере одно значение n,~d + \. Это значение можно вычислить, исходя из того, что

и, = (-2*"-l)/d d + l = -2""+rem(2""+l,d). Величина п представляет собой одно из

d наименьших допустимых значений и, так что

-2-S«,<-2"--d-l (15,а)

и, очевидно.

и <d + l.

(15,6)

Поскольку (14,6) должно выполняться при n = ~d,& (14,а) - для п-п,,хо аналогично (4) получим

--£-<т<-. (1о)

Так как т является наибольшим целым «ислом, удовлетворяющим (16), оно представляет собой ближайшее целое, меньшее 2jd, т.е.

2-t/-rem(2t/)

(17)

Объединяя это выражение с левой частью (16) и упрощая, получим

(18)

2>л,(t/ + rem(2t/))

Доказательство пригодности предложенного в (17) и (18) алгоритма и корректности произведения выполняется аналогично доказательству для положительного делителя и здесь не приводится. Трудности возникают только при попытках доказать, что -2" < m < О. Для доказательства рассмотрите по отдельности случаи, когда d представляет собой отрицательное число, абсолютное значение которого является степенью двойки Для t/ = -2* можно легко показать, что л„=-2"" + 1, p = W+k-l и т = -2""-1 (которое находится в изначально определяемом диапазоне). Для тех d, которые имеют отличный от -2* вид, достаточно просто изменить доказательство, приведенное ранее, при рассмотрении положительного делителя.

Для каких делителей mi-d)-m(d)7

Под m{d) подразумевается множитель, соответствующий делителю d. Если m(-d)--m{d), код для деления на отрицательный делитель может быть сгенерирован путем вычисления множителя для Щ , изменения его знака и генерации кода, аналогичного коду из примера "деления на -7", проиллюстрированному ранее.

Сравнивая (18),с (6), а (17) с (5), можно увидеть, что если значение для -d представляет собой значение для d, но с обратным знаком, то m{-d) = -m{d). Следовательно, m(-d) Ф -m(d) может быть только тогда, когда значение вычисленное для отрицательного делителя, представляет собой наибольшее по абсолютному значению отрицательное число -2"". Такие делители представляют собой отрицательные сомножители г"" +1. Эти числа встречаются очень редко, что иллюстрируется приведенными ниже разложениями.

21= 3-11-331 241 =3-715827883 2+1 = 3-19-43-5419-77158673929 Для всех этих множителей m{-d)~m{d). Вот набросок доказательства. Для d>0

мы имеем = 2""- rf. Поскольку гет( 2"", rf) = rf-l, значение p = W-\ удовлетворяет (6), а следовательно, этому неравенству удовлетворяет и p = W. Однако для rf < О мы имеем л=-2" и rem(2"",rf) = rf-l. Следовательно, ни p = W-1,hh p = W не удовлетворяют (18), так что p>W.

2"-+rem(2"-,t/)-l, d>0, -2"-+Km{f-+U), d<0.

Следовательно, можно вычислить так;

r = 2

d>0, d<0.

= t-\-Km[t,\d\).

Остаток должен вычисляться с использованием беззнакового деления, в соответствии со значениями аргументов. Здесь используется запись гет(г,г/), а не эквивалентная ей Tem{t,d) именно для того, чтобы подчеркнуть, что программа должна работать с двумя

положительными (и беззнаковыми) аргументами.

Исходя из (6) и (18), значение р может быть вычислено из соотношения

2>K(M-rem(2£)),

(19)

после чего m

можно вычислить следующим образом (используя (5) и (17)): 2 +\d\-Tem{2,\d)

(20)

Непосредственное вычисление rem(2,t/) в (19) требует применения "длинного деления" (деление 2W-6HTOBoro делимого на W-битовый делитель и получение W-битовых частного и остатка), причем это длинное деление должно быть беззнаковым. Однако имеется путь решения (19), который позволяет избежать использования длинного деления и может быть легко реализован в обычных языках программирования высокого уровня с использованием только W-битовой арифметики. Тем не менее нам потребуется беззнаковое деление и беззнаковое сравнение.

Вычислить гет(2,г/) можно инкрементно, инициализируя две переменные диг

значениями частного и остатка от деления 2 на \d\ при р = W -1, а затем обновляя значения g и г по мере роста р.

В процессе поиска при увеличении значения р на 1 значения диг изменяются следующим образом (см. теорему D5 (первая формула)):

q = 2*q; г = 2*г:

if (г >= abs(d))

Для того чтобы компилятор мог заменить деление на константу произведением, он должен вычислить для данного делителя d магическое число М и величину сдвига s. Простейший способ состоит в вычислении (6) или (18) для р = W,W +1,... до тех пор, пока условие будет выполняться. Затем из (5) или (17) вычисляется значение т. Магическое число М представляет собой не что иное, как интерпрепщию т как знакового целого числа, а j = р - W .

Описанная ниже схема обрабатывает положительные и отрицательные d с помощью небольшого дополнительного кода, и позволяет избежать арифметических выражений с двойными словами.

Вспомним, что Пс задается следующим образом;