Докажите, что между шагами А5 и А6 алгоритма А можно, не изменяя результата, заменить fv на b~~Fv, где Fv ~ b"fv. (Если JP„-целое и Ь четно, эта операция, по сути, позволяет "урезать" /„ до р + 2 разрядов, запоминая, был ли отброшен любой разряд, отличный от нуля. В результате может быть минимизирована длина регистра, необходимого для сложения на шаге А6.)

6. [20] Если результат выполнения команды FADD равен нулю, каким будет знак регистра гА (если следовать описанию операций арифметического расширителя компьютера MIX, представленному в этом разделе)?

7. [27] Проанализируйте арифметические операции с плавающей точкой с использованием уравновешенной тернарной нотации.

8. [20] Приведите примеры нормализованных восьмиразрядных десятичных чисел с плавающей точкой U и и, для которых сложение влечет за собой (а) исчезновение порядка, (Ь) переполнение порядка, если подразумевать, что для порядков справедливо соотношение О < е < 100.

9. [М24] (У. М. Кахан (W. М. Kahan).) Предположим, что исчезновение порядка приводит к присвоению результату значения "нуль" без какой-либо индикации ошибки. Используя восьмиразрядные десятичные числа с плавающей точкой с избытком нуль и порядком е в интервале -50 < е < 50, найдите такие положительные значения а, Ь, с, d и у, для которых выполняются соотношения (11).

10. [12] Приведите пример нормализованных восьмиразрядных десятичных чисел с плавающей точкой и и и, в процессе сложения которых происходит переполнение при округлении.

► 11. [М20] Приведите пример нормализованных восьмиразрядных десятичных чисел с плавающей точкой и и и, в процессе умножения которых происходит переполнение при округлении.

12. [М25] Докажите, что переполнение при округлении не может происходить в ходе выполнения фазы нормализации при делении чисел с плавающей точкой.

13. [30] Имея дело с "арифметикой интервалов", нежелательно Ькруглять результаты вычислений в формате с плавающей точкой. Скорее, было бы желательно реализовать операции, подобные у и А, которые дают наиболее близкое представление границ сумм:

V < U + V < и Av.

Как модифицировать алгоритмы, описанные в данном разделе, чтобы они подходили для этой цели?

14. [25] Напишите подпрограмму для MIX, которая работала бы с произвольным исходным числом в регистре А, необязательно нормализованным, и преобразовывала бы его в ближайшее целое в формате с фиксированной точкой (или обнаруживала, что число слишком велико по абсолютной величине, чтобы было возможно такое преобразование).

► 15. [28] Разработайте подпрограмму для MIX, которая по заданному числу в формате с плавающей точкой и вычисляет и (mod) 1, а именно и - [и\, округленное до ближайшего числа в формате с плавающей точкой. Подпрограмма должна быть увязана с остальными подпрограммами этого раздела. Обратите внимание на то, что когда и - очень малое отрицательное число, и (mod) 1 должно быть округлено таким образом, чтобы результат был равен единице (хотя и mod 1 по определению всегда должно давать результат, меньший единицы как действительного числа).

16. [НМ21] (Роберт Л. Смит (Robert L. Smith).) Разработайте алгоритм для вычисления действительной и мнимой частей комплексного числа (а + Ы)/{с + di) по заданным действительным числам в формате с плавающей точкой а, Ь, с и d. Постарайтесь избежать

вычисления (? +d, поскольку это может привести к переполнению порядка даже тогда, когда с или d приблизительно равно квадратному корню максимально возможного числа в формате с плавающей точкой.

17. [40] (Джон Кок (John Соске).) Реализуйте идею расширения диапазона представления чисел в формате с плавающей точкой, определив однословное представление, в котором точность дробной части уменьшается по мере того, как увеличивается значение абсолютной величины порядка.

18. [25] Представим себе двоичный компьютер с 36-битовым форматом слова, в котором положительные двоичные числа в формате с плавающей точкой представлены в виде (Oeies... eg/i/s.. ./27)2; здесь (eie2... 68)2 есть избыток (10000000)2 порядка и (/1/2.. ./27)2 есть 27-битовая дробная часть. Отрицательные числа в формате с плавающей точкой представлены двумя дополнениями соответствующих положительных представлений (см. раздел 4.1). Таким образом, 1.5 имеет вид 201\600000000 в восьмеричных обозначениях, а -1.5 имеет вид 576\200000000; восьмеричные представления 1.0 и -1.0 есть 201 \4OOOOOOOO и 576\400000000 соответственно. (Вертикальные черточки использованы здесь для отображения границы в машинном слове между порядком и дробной частью.) Учтите, что бит fi для нормализованного положительного числа всегда равен 1, в то время как для отрицательного он почти всегда равен нулю; исключениями являются представления чисел -2*.

Предположим, что точный результат операции в формате с плавающей точкой имеет в восьмеричном представлении вид 572\740000000\0Г, эта отрицательная 33-битовая дробная часть должна быть нормализована и округлена до 27 бит. Если сдвигать ее влево до тех пор, пока первый бит дробной части не станет равным нулю, получится 576\000000000\20. Но это приведет к округлению до неправильного значения 576\000000000; в данном случае возникла "перенормализация", поскольку правильный результат-575\400000000. С другой стороны, если начать (в какой-нибудь другой задаче) со значения 5721740000000 \ 05 и остановиться до возникновения перенормализации, получится 575\400000000\50. Этот результат округляется до ненормализованного числа 575\400000001\ последующая нормализация приведет к результату 576\000000002, в то время как верный результат - 576\000000001.

Придумайте простое, но правильное правило округления, которое разрешит эту дилемму для такой машины (но принятый формат с двумя дополнительными представлениями должен остаться в неприкосновенности).

19. [24] Каково время выполнения подпрограммы FADD в программе А в терминах, отображающих характеристики исходных данных? Каково максимальное время выполнения для любых исходных данных, которые не приводят к переполнению или потере значимости порядка?

Округленные числа всегда лгут. - СЭМЮЭЛЬ ДЖОНСОН (SAMUEL JOHNSON) (1750)

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

- ТОМАС ДЖЕФФЕРСОН (THOMAS JEFFERSON) (1824)

4.2.2. Точность арифметических операций с плавающей точкой

Вычисления над числами в формате с плавающей точкой неточны по самой своей природе, и программисту нетрудно столь неудачно организовать их выполнение, что полученные результаты будут почти полностью состоять из "шума". Одна из главных проблем численного анализа состоит в анализе точности результатов тех или иных численных методов; сюда же относится и проблема "степени доверия": мы не знаем, насколько правильны результаты вычислений на компьютере. Пользователи-новички решают эту проблему, доверяя компьютеру, как непогре-шимому авторитету; они склонны считать, что все цифры напечатанного ответа являются значащими. У пользователей, лишенных этих иллюзий, подход прямо противоположный: они неизменно опасаются, что полученные результаты весьма далеки от истинных. Многие из серьезных математиков пытались строго проанализировать последовательность операций с плавающей точкой, но, обнаружив, что задача слишком сложна, удовлетворялись правдоподобными рассуждениями.

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

Грубый (но зачастую вполне приемлемый) способ, с помощью которого можно охарактеризовать выполнение операций арифметики с плавающей точкой, основан на понятии значащих разрядов или относительной ошибки. Если точное вещественное число X в компьютере представляется посредством приближения х = х{1 + е), то величина f = {х - х)/х называется относительной ошибкой приближения. Грубо говоря, при выполнении вычислений в формате с плавающей точкой операции умножения и деления не слишком увеличивают относительную ошибку, но вычитание почти равных величин (и сложение и ф v, где и почти равно -v) может увеличить ее значительно. Итак, общее эмпирическое правило таково: существенной потери точности можно ожидать от сложения и вычитания указанного вида, но не от умножения и деления. С другой стороны, ситуация довольно парадоксальная и ее нужно правильно воспринимать, поскольку "плохое" сложение и вычитание всегда выполняется с великолепной точностью! (См. упр. 25.)

Одним из следствий возможной ненадежности сложения в формате с плавающей точкой является нарушение закона ассоциативности:

{ифи)фъифиф{ифъи) для многих и,V,W. (1)

Например:

(11111113. е -11111111.) ф 7.5111111 = 2.0000000 Ф 7.5111111 = 9.5111111; 11111113. ф (-11111111. ф 7.5111111) = 11111113. Ф -11111103. = 10.000000.

(Все примеры в этом разделе приводятся в восьмиразрядном десятичномформате с плавающей точкой с представлением порядков посредством прямого указания места расположения десятичной точки. Напомним, что, как и в разделе 4.2.1, символы ф, Э, ®, 0 используются для обозначения операций в формате с плавающей точкой, соответствующих точным операциям -, х, /.)