Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 71
Текст из файла (страница 71)
С. СашрЬе!1, хР!оас!пй ро!пс орегас!опя в Р!аппт8 а Ссипрн!ег Яузгшп, ег)!гег) Ьу %. ВисЬЬо!х (Хен ЪЪг)с МсОгатг-Н!!1, 1962), 92-121, А. Рас(ейэ, 1ВМ Яуэсетэ Х 7 (1968), 22-29. Дополнительный список источников, в основном, имеющих отношение к анализу точности вычислений в формате с плавающей точкой, представлен в разделе 4.2.2. Поистине революционные изменения в аппаратной реализации арифметики с плавающей точкой произошли, когда большинство изготовителей компьютеров приняли к исполнению стандарт АХЯ1/1ЕЕЕ Ясапдагг[ 754 в конце 80-х годов. (См. 1ЕЕЕ М!сто 4 (1984), 86 — 100; %, Л.
Спбу, Сотр. Яс1 и Ягаг!эг!сэ: Яутр. ол йЬе 1лгегуасе 15 (1983), 133-139; %. М. КаЬап, АВ!и!/М!сто Игезг-83 СовЕ Весогг! (1983), Рарег 16/1; П. Со!г[Ьегй, Согпрпгтб Яиггеуэ 23 (1991), 5 — 48, 4И; %. Л. Сос)у апг! Л. Т. Соопеп, АСМ Тгалэ. Магй. Яойтгаге 19 (1993), 443-451.) Компьютер Ю?1Х, который эааенпт ?411 в следующем издании данной кнпггг, Ф будет полностью соогвет«твовагь этому стандарту. УПРАЖНЕНИЯ 1. [!0] Как будут выглядеть число Авогадро и постоянная Планка (3), если их представить в виде четырехразрядных чисел с плавающей точкой по основанию 100 с избытком 50? (Именно таким было бы представление в машине И13, как в (4), если бы размер байта равнялся 100,) 2. [?8] Предположим, порядок е находится в интервале 0 < е < Е.
Каковы наибольшее и наименьшее положительные значения, которые могут быть записаны как р-разрялные числа с плавающей точкой по основанию Ь с избытком д? Каковы наибольшее и наименьшее положительные значения, которые могут быть представлены в виде таких нормализованных чисел? 3. [?!] (К. Пузе (К. Епзе), 1930.) Покажите, что, работая с нормализованными двоичными числами с плавающей точкой, можно немного увеличить точность без увеличения объема используемой памяти: р-разрядную дробную часть можно представлять при помощи всего лишь р — ! разрядов машинного слова, если чуть.
чуть уменьшить интервал значений порядка, 4. [?б] Пусть Ь = 1О, р = 8. Какой результат даст алгоритм А для операции (50, + 98765432) 9 (49, +.ЗЗЗЗЗЗЗЗ), для операции (53, †.99987854) В (54, +.10000000) и для операции (45, †.50000001) !О (54, +.10000000)? 5. [84] будем говорить, что х р (по отношению к данному основанию Ь), если х и р— действительные числа, удовлетворяющие следующим условиям: [х/Ь] = [р/Ь]; хшобЬ=О с=в ушог!ЬмО; О<хшобЬ< -'Ь ся, 0 < ршобЬ< эЬ; хпюбЬ= 1Ь с=в ршог!Ь= эЬ; -Ь < х шобЬ < Ь е=~ -Ь < р пюб Ь < Ь. Докажите, что между шагами АЬ и Аб алгоритма А можно, не изменяя результата, заменить ~, на Ь " ~г„где Р„Ь"'~э~„. (Если Є— целое и Ь четно, эта операция, по сути, позволяет "урезатьэ у„до р + 2 разрядов, запоминая, был ли отброшен любой разряд, отличный от нуля.
В результате может быть минимизирована длина регистра, необходимого для сложении иа шаге Аб.) 6. [20] Если результат выполнения команды Г100 равен нулю, каким будет знак реги- стра гА (если следовать описанию операций арифметического расширителя компьютера Н11, представленному в этом разделе)? 7. [27) Проанализируйте арифметические операции с плавающей точкой с использова. нием уравновешенной териарной нотации. 6. [20] Приведите примеры нормализованных восьмиразрядных десятичных чисел с пла- вающей точкой и и о, для которых сложение влечет за собой (а) исчезновение порядка, (Ь) переполнение порядка, если подразумевать, что для порядков справедливо соотношение 0 < е < 100. й.
[М24] (У, М, Кахвн (%. М, Кайап).) Предположим, что исчезновение порядка приво- дит к присвоению результату значения "нуль" без какой-либо индикации ошибки. Исполь- зуя восьмиразрядные десвтичные числа с плавающей точкой с избытком нуль и порндком е в интервале -50 < е < 50, найдите такие положительные значения а, Ь, с, д и у, для которых выполняются соотношения (11). 10. [12] Приведите пример нормализованных восьмиразрядных десятичных чисел с пла- вающей точкой в и е, в процессе сложения которых происходит переполнение прн округ- лении, ь 11. [М20] Приведите пример нормализованных восьмиразрядных десятичных чисел с плавающей точкой и и е, в процессе умножения которых происходит переполнение при округлении.
12. [М25] Докажите, что переполнение при округлении не может происходить в ходе выполнение фазы нормализации при делении чисел с плавающей точкой. 13. [80] Имея дело с "арифметикой интервалов", нежелательно округлять результаты вычислений в формате с плавающей точкой. Скорее, было бы желательно реализовать операции, подобные ~7 и Й, которые дают наиболее близкое представление границ сумм: Как модифицировать алгоритмы, описанные в данном разделе, чтобы они подходили для этой цели? 14.
[25] Напишите подпрограмму для Н11, которая работала бы с произвольным исходным числом в регистре А, необязательно нормализованным, и преобразовывала бы его в ближайшее целое в формате с фиксированной точкой (яли обнаруживала, что число слишком велико по абсолютной величине, чтобы было возможно такое преобразование). ° 15. [28] Разработайте подпрограмму для Н11, которая по заданному числу в формате с плавающей точкой и вычисляет и Я?) 1, а именно о — [в], округленное до ближайшего числа в формате с плавающей точкой, Подпрограмма должна быть увязана с остальными подпрограммами этого раздела.
Обратите внимание на то, что когда и — очень малое отрицательное число, и Я2) 1 должно быть округлено таким образом, чтобы результат был равен единице (хотя и шоб 1 по определению всегда должно давать результат, меньший единипы как действительного числа). 16. [НМ21] (Роберт Л. Смит (КоЬегг Ь. Бгайй).) Разработайте алгоритм для вычисления действительной и мнимой частей комплексного числа (а + М)у(с + Ж) по заданным действительным числам в формате с нэавающей точкой а, Ь, с и 4. Постарайтесь избежать вычисления с + о~, поскольку зто может привести к переполнению порядка даже тогда, когда: (с( или Щ приблизительно равно квадратному корню максимально возможного числа в формате с плавающей точкой. 17. (401 (Джон Кок (5оЬп Сос2е).) Реализуйте идею расширении диапазона представления чисел в формате с плавающей точкой, опрещшив сдкословное представление, в котором точность дробной части уменьшается по мере того, как увеличивается значение абсолютной величины порядка.
18. (25) Представим себе двоичный компьютер с 36-битовым форматом слова, в котором положительные двоичные числа в формате с плавающей точкой представлены в виде (Ое~ею .. еэлЬ...узт)м здесь (е ~ем .. ез)з есть избыток (10000000)а порядка и (луь .Ую)з есть 27-битовая дробная часть. Отрицательные числа в формате с плавающей точкой представлены двумя дополнениями соответствующих положителькых представлений (см. раздел 4.1). Таким образом, 1.5 имеет вид 201 )600000000 в восьмеричных обозначениях, а -1.5 имеет вид 576)200000000, восьмеричные представления 1Д и — 1.0 есть 201~400Р00000 и 576) 400000000 соответственно.
(Вертикальные черточки использованы здесь для отображения границы в машинном слове между поридком и дробной частью.) Учтите, что бит л для нормализованного положительного числа всегда равен 1, в та время как для отрицательного он почти всегда равен нулю; исключениями ивляются представления чисел -2». Предположим, что точный результат операции в формате с плавающей точкой имеет в восьмеричном представлении вид 572(740000000(01; зта отрицательная 33-битовая дробная часть должна быль нормализована и округлена до 27 бит, Если сдвигать ее влево до тех пор, пока первый бит дробной части не станет равным пулю, получится 576) 000000000(20.
Но зто приведет к округленюо до неправильного значения 576(000000000; в данном случае возникла "перенормализация", поскольку правильный результат — 575(400000000. С другой стороны, шли начать (в какой-иибудь другой задаче) со значения 572(740000000)05 и остановиться до возникновения перенормализации, получится 575(400000000(50. Этот результат округляется до ненормализованного числа 575~400000001; послелующая нормализация приведет к результату 576~000000002, в то время как верный результат— 576(ВОООРРОВЛ Придумайте простое, но правильное правило округления, которое разрешит зту дилемму для такой машины (но принятый формат с двумя дополнительными представлениями должен остаться в неприкосновенности). 19.
(24) Каково время выполнения подпрограммы Райй в программе А в терминах, отображающих характеристики исходных данных? Каково максимальное время выполнения для любых исходных дшшых, которые не приводит к переполнению или потере значямости порядка7 Округленные числа всегда лгут. — сзмюэлыРкОнсОн (ьАм0е$.
эОнмбОН) (1750) Я буду говорить в округленных числах, ие абсолютно точно, ио ие настолько далеко от истины, чтобы изменить реальный результат. — ТОМАС ДМСЕПИРЕРСОН (ТНОМА5 ЗЕЕРЕйБОМ) (1824) 4.2.2. Точность арифметических операций с плавающей точкой Вычисления над числами в формате с плавающей точкой неточны по самой своей природе, и программисту нетрудно столь неудачно организовать их выполнение, что полученные результаты будут почти полностью истаять из "шума". Одна из главных проблем численного анализа состоит в анализе точности результатов тех или иных численных методов; сюда же относится и проблема "степени доверия": мы не знаем, насколько правильны результаты вычислений на компьютере.
Пользователи-новички решают эту проблему, доверяя компьютеру, как непогрешимому авторитету; они склонны считать, что все цифры напечатанного ответа являются значащими. У пользователей, лишенных этих иллюзий, подход прямо противоположный: они неизменно опасаются, что полученные результаты весьма далеки от истинных. Многие из серьезных математиков пытались строго проанализировать последовательность операций с плавающей точкой, но, обнаружив, что задача слишком сложна, удовлетворялись правдоподобными рассуждениями.
Полное исследование методов анализа ошибок выходит, разумеется, за рамки настоящей книги, однако некоторые из характеристик ошибок, возникающих при вычислениях в формате с плавающей точкой, мы здесь все.таки рассмотрим. Наша цель — выяснить, как выполнить операции с плавающей точкой таким образом, чтобы, сохраняя достаточно высокий уровень достоверности, упростить, насколько это возможно, анализ распространения ошибки. Грубый (но зачастую вполне приемлемый) способ, с помощью которого можно охарактеризовать выполнение операций арифметики с плавающей точкой, основан на понятии значащих разрядов или ошгюсишельной ошибки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
