РАЗДЕЛ 4.2.1

1. N = (62, +.60 22 14 00); h = (37, +.66 26 10 00). Обратите внимание на то, что значение lOh имело бы вид (38,+.06 62 61 00).

2. 6-(1 - Ь-р), б--р; 6-(1 - Ь-"), 6--.

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

4. (51,+.10209877); (50,+.12346000); (53,+.99999999). Если бы первый операнд равнялся (45, -.50000000), то третий ответ был бы (54, +.10000000), поскольку Ь/2 нечетно.

5. Если X ~ у и тп есть целое число, то тЪ + х ~ тЬ + у. Более того, если рассмотреть все возможные случаи, то окажется, что из ж ~ у следует х/Ь ~ у/Ь. Другое важное свойство состоит в том, что X и у будут округлены до одного и того же целого при любых X ~ у.

Теперь, если b~~F,i ф /i,, необходимо получить (Ь/i,) mod 6 ф 0. Следовательно, преобразование оставляет неизменным до тех пор, пока бц - > 2. Поскольку и не нормализовано, оно отлично от нуля и Д + Л! > - > Ь~. Ведущий, отличный от нуля разряд /„ + jv должен находиться не более чем на два разряда правее разделяющей точки, и операция округления преобразует {fu + Л) в целое, где j < 1. Доказательство будет завершено, если показать, что 6P+•(„ + г,) ~ 6-(Д+6~~Р„). Из предыдущего абзаца имеем b{U + U) ~ 6р+/„ + К, = 6+(Д + b~~F,), из чего следует искомый результат для всех j < 1. Аналогичное замечание справедливо и в отношении шага М2 алгоритма М.

Обратите внимание, что, когда 6 > 2 четное, такое целое число Ft, существует всегда; но если 6 = 2, потребуется р + 3 бит (полагаем 2F„ целым). Если 6 нечетно, то целое F„ существует всегда, кроме случая деления в алгоритме М, когда возможен остаток 6.

6. (Рассмотрите случай, когда е„ = Ci,, /„ = в программе А.) Регистр А сохранит предыдущее значение знака, как и при выполнении команды ADD.

7. Будем говорить, что число нормализовано тогда и только тогда, когда оно равно нулю или его дробная часть находится в диапазоне < / < 5. Аккумулятор на (р + 1) разрядов вполне подойдет для операций сложения и вычитания; округление (кроме случая деления) эквивалентно отбрасыванию лишних разрядов. Кажется, получилась очень привлекательная система! Можно использовать представление чисел порядком с избытком нуль, вставленным между первым и последующими разрядами дробной части и дополненным, если дробная часть отрицательна. Так что сохраняется порядок, принятый для чисел с фиксированной точкой.

8. (а) (06, +.12345679) ® (06, -.12345678), (01, +.10345678) ® (00, -.94000000); (Ь) (99, +.87654321) ф оно же, (99, +.99999999) ® (91, +.50000000).

9. о = с = (-50,+.10000000), 6 = (-41,+.20000000), d = (-41,+.80000000), у = (11,+.10000000).

10. (50, +.99999000) ® (55, +.99999000).

11. (50, +.10000001) ® (50, +.99999990).

12. Если О < \fu\ < М, то \fu\ < \fv\- b-"; следовательно, 1/6 < \fu/fv\ < 1 - Ь"71М < 1-6-". Если О < М < М, имеем 1/6 < 1Д/М/6 < ((1 - 6-)/(1/6))/6 = 1 - б"".

13. См. J. Michael Yohe, IEEE Transactions С-22 (1973), 577-586, a также упр. 4.2.2-24.

14. FIX STJ 9F Подпрограмма ПТ-в-ФТ.

STA TEMP

LDl TEMP(EXP) rll <- e.

SLA 1 rA<-± 0.

JAZ 9F DECl 1

CMPA =0=(1:1) JE ♦-4 ENNl -Q-4,1 JIN FIXOVFLO ENTX 0 SRAX 0,1 CMPX =l 2= JL 9F JG ♦+2 JAO 9F

STA ♦+1(0:0) INCA 1 9H JMP ♦

15. FP

EXITF OFLO TEMP 0 1

TEMP(EXP) Q

STJ JOV STA ENTX SLA LD2 DEC2 J2NP *+3 SLA 0,2 ENT2 0 JANN IF ENN2 0,2 SRAX 0,2 ENT2 0 JXNZ *+3 JAZ *+2 INCA 1 ADD WMl INC2 Q JMP NORM EQU 1(1:1)

Нуль на входе?

Если ведущий байт равен нулю, снова сместить влево.

Абсолютное значение слишком велико?

В некоторых случаях становится нечетным,

поскольку 6/2 четно. При необходимости округлить. Add ±1 (переполнение невозможно). Выход из подпрограммы.

Подпрограмма для выделения дробной части. Снятие блокировки переполнения. TEMP <- и.

гА <- fu-rI2 <r- ей.

Удалить целую часть и.

Дробная часть отрицательна: найти ее дополнение.

Добавить размер слова минус единица. Подготовка к нормализации результата. Нормализовать, округлить и выйти из подпрограммы.

WM1 CON 8В-1,8В-1(1:4) Размер слова минус единица 16. Если с > d, то установить

r-<-d0c, S(-c®(r®d); ж (а ф (6 ® г)) 0 s, ?/<-(6 е (а ® г)) 0 s.

В противном случае установить

г <- с 0 d, S d е (г ® с); ж <- ((о ® г) ® 6) 0 s, ?/ ((6 ® г) G о) 0 s.

Тогда X + iy есть искомая аппроксимация (а + bi)/{c + di). [САСМ 5 (1963), 435. Другие алгоритмы для выполнения арифметических операций с комплексными числами и вычисления соответствующих функций описаны в работе Р. Wynn, BIT 2 (1962), 232-255; см. также Paul Friedland, САСМ 10 (1967), 665.]

17. (См. Robert Morris, IEEE Transactions C-20 (1971), 1578-1579.) Для такой системы анализ ошибки более сложен, поскольку здесь предпочтительнее использовать арифметику интервалов.

18. Для положительных чисел решение таково. Сдвигать дробную часть влево до тех пор, пока не окажется, что /i = 1; затем округлить, затем, если дробная часть равна нулю (переполнение при округлении), снова сдвинуть вправо. Для отрицательных чисел решение таково. Сдвигать дробную часть влево до тех пор, пока не окажется, что /i = 0; затем округлить, затем, если дробная часть равна нулю (исчезновение значимости при округлении), снова сдвинуть вправо.

19. (43 + [ct, < Си] - [переполнение дробной части] - 10 [результат - нуль] + 4 [абсолютная величина округлена до] + [первый округленный разряд равен ] + 5 [округленные разряды равны 0 ... 0] + 7 [переполнение при округлении] + 7N + (11 [ Л > О ] - 1) [гХ принимает ненулевые разряды])и, где N есть число сдвигов влево при нормализации. Максимальное время 73и получается, если, например,

и = +50 01 00 00 00, V = -46 49 99 99 99, b = 100.

[Учитывая данные из раздела 4.2.4, время будет иметь порядок 45.5и.]

РАЗДЕЛ 4.2.2

1. uev = u®-v = -v®u = -{v ф -и) = -{v е и).

2. ифх > ифО = и, как следует из (8), (2), (6), поэтому снова в силу (8) (ифа;)Ф« > u®v. Аналогично из (8) и (6) вместе с (2) следует, что (и ф х) ф (d ф у) > (и ф х) ф v.

3. и = 8.0000001, V = 1.2500008, w = 8.0000008; (и ® w) ® w = 80.000064, и ® (w ® w) = 80.000057.

4. Да; пусть Х/и к V - W, где v велико.

5. Не всегда, например для чисел и = w = 9 в десятичной системе.

6. (а) Да. (Ь) Только для 6+р < 4 (попробуйте проверить с и = 1 -6""). Но см. упр. 27.

7. Если и и V - последовательные числа с плавающей точкой, u®v = 2u или 2v. Когда это 2w, мы часто получаем и® ф«® < 2v®. Например, и = (.10 ... 001)2, v = (.10 ... 010)2, и ф W = 2w и и® + W® = (.10 ... 011)2.

8. (а) ~, ) (Ь) ~, «; (с) ~, й;; (d) ~; (е) ~.

9. \u-w\ < \u-v\-\-\v-w\ < 6imin(6"-9,b""-9)+62min(6=--9,b""-«) < 6ib"-«+626"-« < (ei + ег) тах(Ь",Ь"-). В общем случае усилить этот результат нельзя. Например, можно было бы взять Сц очень малым по сравнению с обоими порядками и e„, но это означало бы, что u - w слишком велико при сделанных предположениях.

10. Если Ор > 1 и ai > , получим {.ах ... ар-хар)ь ® (.9 ... 99)ь = {.ах ... ар-х{ар - 1))ь; здесь "9" есть Далее, {.ах... ар-хар)ь <S (1.0 ... 0)ь = {.ах .. ар-хО)ь, так что, если Ь>2и ар> l + [ai>], умножение оказывается не монотонной операцией. Но в случае, когда 6 = 2, используя то же самое рассуждение, можно доказать, что умножение является монотонным. Очевидно, "некий компьютер" имеет 6 > 2.

11. Можно положить без ущерба для общности рассуждений, что х есть целое, О < х < 6". Если е < О, то t = 0. Если 0<е<р, тох -t имеет не более р+1 разрядов, причем наименее значимый равен нулю. Если е > р, то х - t = 0. [Результат справедлив и при более слабой исходной посылке t < Ь; в этом случае можно было бы получить х - t = Ь, если е > р.]

12. Предположим, что Сц = р, е„ < О, и > 0. Случай 1: и > ftP"". Случай (1, а): w = и+ 1, w > i, е„ = 0. Тогда и = и или и + 1, w = 1, и" = и, v" = 1 или 0. Случай (1, Ь):