Далее, и < 2", поскольку 2 -1 является наибольшим представимым целым числом. Следовательно, член-ошибка 2п/(3-2") меньше 1/3 (и это значение неотрицательно), Tai

что в соответствии с теоремой D4 из раздела 9.1 получаем д = [п/Ъ}, что и требовалоа

получить (формула (1) в том же разделе 9.1).

В случае п<0 к частному добавляется 1. Следовательно, приведенный выше код вычисляет в этом случае величину

2Ч2 и

3 2-

+ 1 =

2"и+2п + 3-2*

3-2=

2"п + 2п + 1

3-2-

Здесь была использована теорема D2, Следовательно,

При -2 < и < -1 получаем

и 2я + 1

зз-г

з"3-2

з-г 3-2"

Таким образом, ошибка отрицательна и больше, чем -1/3, а значит, в соответствии с теоремой D4 д = \п/У\, что и является искомым результатом (формула (1) из раздела 9.1).

Итак, установлено, что вычисленное значение частного корректно. Тогда корректно и значение остатка, поскольку остаток должен удовлетворять соотношению n = qd + r. Умножение на 3 не может вызвать переполнения (так как -2/3Sqi<(2"-l)/3), а вычитание не может привести к переполнению в связи с тем, что результат должен находиться в диапазоне от -2 до +2.

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

На многих современных RISC-компьютерах частное может быть вычислено так, как показано выше, за девять-десять тактов, в то время как команда деления может потребовать 20 тактов или около того.

Деление на 5

Дня деления на 5 хотелось бы использовать код того же типа, что и дяя деления на 3, но, понятно, с множителем (2" + 4)/5. К сожалению, при этом ошибка оказывается слишком

большой и результат отличается на единицу от точного примерно для пятой части значений пй 2**. Но оказывается, можно использовать множитель (2" +3)/5 и добавить к коду команду знакового сдвига вправо. В результате получается следующий код:

Доказательство. Команда mulhs дает 32 старших бита 64-битового произведения, после чего код знаково сдвигает полученное значение вправо на одну позицию. Это действие эквивалентно делению 64-битового произведения на iP" и вычислению функции floorO от полученного результата. Таким образом, для и а О приведенный код вычисляет

2"+3 и

5 1-

п Зп 55-2

Для О S и < 2" ошибка составляет ЗлДз • 2"); это значение неотрицательно и меньше, чем 1/5, так что в соответствии с теоремой D4 q =[п/5J • При и < О приведенный выше код вычисляет значение

Здесь член-ошибка отрицателен и превышает -1/5, так что qlnfS]. Корректность

вычисленного остатка доказывается так же, как и в случае деления на 3. Как и ранее, команда улнолсенмя на непосредственно заданное значение может быть заменена - в данном случае сдвигом влево на две позиции и сложением.

Деление на 7

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

получаем следующий код для деления на 7:

Доказательство. Важно обратить внимание на то, что команда "add q,q,n не может вызвать переполнения. Дело в том, что дни имеют противоположные знаки; это связано с умножением на отрицательное число. Таким образом, это "компьютерное сложение" выполняется так же, как и обычное арифметическое сложение, и для и > О приведенный выше код вычисляет

2n + 5n-7-2-n + 7-2«n

(здесь при преобразованиях использовано следствие из теоремы D3).

10.3. ЗНАКОВОЕ ДЕЛЕНИЕ И ВЫЧИСЛЕНИЕ ОСТАТКА ДЛЯ ДРУГИХ СЛУЧАЕВ

Для Ойп<2" ошибка, составляющая Snjll-l), неотрицательна и меньше 1/7, так что д = [п/7J .

Для и < О приведенный выше код вычисляет значение

2+5 ,3а

+ 1 =

5я + 1 7"7.2"

В этом случае ошибка не положительна и больше -1/7 , так что =[«/?].

Команда умноженш на непосредственно заданное значение может быть заменена сдвигом влево на три позиции и вычитанием.

10.4. Знаковое деление на делитель, не меньший 2

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

Некоторые из приводимых доказательств весьма сложны, так что читайте дальнейший материал внимательно и не забывайте о том, что работаете со словом размером W.

Итак, пусть дан размер слова W й 3 и делитель 2 S rf < 2*" и требуется найти наименьшее целое О < m < 2* и целое р SIV , такие, что

для о < и < 2* и

для -гйпй-Х.

(1,а)

(1,6)

Найти наименьшее целое т необходимо потому, что меньший множитель может потребовать меньшую величину сдвига (возможно, 0) либо привести к коду наподобие кода из примера "деление на 5", но не "деление на 7". Требование тй2 - \ обеспечивает не большее количество команд, чем в примере деления на 7 (т.е. с множителем в диапазоне от 2*" до 2* -1 можно справиться с помощью дополнительной команды сложения, как это было сделано в примере деления на 7, но предпочтительнее обойтись меньшими множителями). Требование p>W нужно постольку, поскольку генерируемый код выделяет левую половину произведения тп, что эквивалентно сдвигу вправо на W позиций. Таким образом, общий сдвиг вправо составляет не менее W позиций.

Есть определенное различие между множителем т и "магическим числом", обозначаемым как М. Магическое число - это значение, которое используется в команде умножения и задается следующим образом:

\т, 0йт<2*\

lm-2", 2-<m<2*.

В силу того, что соотношение (1,6) должно выполняться при n = -d, т.е. -mdJ2 +\ = -\, получаем

>1.