Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 76
Текст из файла (страница 76)
Е. Ксшсй. Ьэб Ргос. Х,ейаэ 3 (1975), 84-87, 164. Использовать арифметику ненормализованных чисел с плавающей точкой рекомендовали Ф. Л. Бауэр н К. Замельзон в упомянутой выше статье; независимо ее использовал Дж. В. Карр (1. 19. Сагг 1П) из Мичиганского университета (1953 г.). Несколькими годами позже был спроектирован кок пьютер МАХ1АС 1П с аппаратной реализацией арифметики обоих типов (см. Н. Ь.
ЛяЬепЬигяг и К. Месгоройя, 1АСМ 6 (1959), 415-428, 1ЕЕЕ Тгапя. ЕС-12 (1963), 896 — 901; Н. Ь. АяЬепЬигж, Ргос. Бргтй,Уо!и» Сотрисег СовЕ 21 (1962), 195-202). Среди других других ранних работ, касающихся ненормализованной арифметикп, нужно также упомянуть статьи Н. 1.. Огау, С. Нагг!яоп, дг., Ргос. Еаягегп Ло!пг Сотригег СопГ. 16 (1959), 244-248, н ЪУ. О. %адеу, ИАСМ 7 (1960), 129 — 139. О ранних исследованиях в области арифметики интервалов речь идет в работах А. О!ЬЪ, САСМ 4 (1961), 319-320; В. Л. СЬагсгея,,7АСМ 13 (1966), 386-403, и книге 1псегкя! Апа!угИя Ьу Иашоп Е.
Мооге (Ргепйсе-НаИ, 1966). Последующий "расцвет" в этой области приводится в более поздней книге Мура (Мооге) Ыейодя апс! Арр!кайопя о1 1пгегга! Апа!угИя (81АМ, 1979). Расширение языка Рааса), допускающее использование переменных наподобие "!псегтаГ', разработано в Университете Карлсруэ в начале 80-х годов. Описание этого языка, который включает и множество других функций, ориентированных на научные расчеты, приведено в работе Раяса1-ИС (Асабеш!с Ргеяя, 1987); авторы — Вохлендер (ВоЫепдег), Ульрих (ПИг!сЬ), Вольф фон Гуденберг (ЧЪИГ топ Оис!епЬегй) и Ролл (Най). Книга П1г!сЬ КийясЬ, Огипс!!айеп с!ея пнтепясЬеп ИесЬпепгс Майета!1ясЬе Ве8гйпс(ипя с(ег ИесЬпегапйшейй (МаппЬепп: В!Ы. 1пяк, 1976) полностью посвящена исследованию систем арифметики в формате с плавающей точкой. (См. также статью Кулиша (КийясЬ) в журнале 1ЕЕЕ Тгапа С-26 (1977), 610-621, и его более позднюю работу в соавторстве с У.
Л. Миранкером (%'. 1,. Мйапйег), озаглавленную Сотригег АпйтеНс ш ТЬеогу н Ргасйсе (Ыеж Уог1с: Аеас(ет!с Ргеяя, 1981).) Прекрасный обзор наиболее свежих работ, касающихся анализа точности выполнения расчетов в формате с плавающей точкой, появился в книге Х. д. Н!8Ьшп, Ассигасу и ИсаЫИГу оГ Митепса! А!8огИЬтя (РЫ1абе)рЫа: 81АМ, 1996). УПРАЖНЕНИЯ Замечание. Если не оговорено противное, предполагаются действия над нормализованными числами в формате с плавающей точкой.
1. (М!8) Докажите, что тождество (7) следует иэ соотношений (2)-(б). 2. [М30] Используя тождества (2) -(8), докажите, что (и Ю х) Ж (е З р) > а Ю е, каковы бы ни баши х> 0 и 9>0. 3. [М80] Найдите восьмиразрядные десятичные числа с плавающей точкой и, е и ш, для которых и З («Зю);4 (и Зе) З ш, причем ни при одном из этих вычислений не происходит ни переполнения, ни исчезновения порядка.
4. [10] Можно ли найти числа с плавающей точкой и, в я ш, для которых при вычислении и З (е З ш) происходило бы исчезновение порядка, а при вычислении (и З е) З ш не происходило? б. [МЙО] Выполняется ли Лля всех чисел с плавающей точкой и и е ~ О равенство аЗ и = и З (1 З е) таким образом, что не возникает ни переполнения, пи исчезновения порядка? 6.
[Мйй] Для каждого иэ слщгующвх двух соотношений вмясиите, выполняется ли оио тождественно для всех чисел а в формате с плавающей точкой: (а) О З (О З и) = а; (Ь) 1З(1Зи) =и. 7. [М81] Пусть аОэ означает иЗа. Найдите такие бинарные числа с плаваэицей точкой и и и, для которых (и З е)Оэ > 2(иОэ+ «Оэ). 8.
[20] Пусть с = 0.0001; какое кз соотношений и .С е (с), и е (с), а 1- е (с). а » -е (с) выполняется для следующих пар восьмирвзрядных десятичных чисел с плавающей точкой с избытком О? а) и = (1, +.31415927), е = (1, +.31416000); Ь) а = (О, +.99997000), е = (1, +.10000039); с) а = (24, +.60221400), в = (27, +.00060221); 6) а = (24, +.60221400), е = (31, +.00000006); е) и = (24, +.60221400), е = (28, +.00000000). 9.
[Мйй] Докажите утверждение (33) и объясните, почему его нельзя усилить до им (с~ + сэ). э 10. [М85] (У. М. Казан (1Ч. М. КаЬап).) На некотором компьютере неправильно выполняется округление пря арифметических операциях над числами в формате с плавающей точкой, и фактически программа умножения принимает во внимание только первые р значащих разрядов 2р-разрядного произведения 1 1„. (Таким образом, если 1 1, < 1/«, иэ-эа последующей нормализации наименее значимый разряд в а З е всегда оказывается равным нулю.) Покажите, что зто приводит к утрате монотонности умножения, т. е.
что существуют такие положительные нормализованные числа с плавающей точкой а, е и 1«, что на этом компьютере и < е, но а З ш > е З ш. 11. [М80] Докажите лемму Т. 12. [М34] Докажите теорему В и (46), если ]е„— е [ > р. е 13. [Мйб] Некоторыеязыкипрограммирования(идаженекоторыекомпьютеры) оперируют только числами в формате с плашющей точкой, ие выделяя в отдельную группу точные операции иаа целыми числами, Есэи желательны и операции нвд целыми числами, можно, естественно, представить их в формате с плавающей точкой. Тогда, если операции арифметики с плавающей точкой удовлетворяют базовым соотношениям (9), можно считать, что все операции выполняются точно в том смысле, что, если опершщы представлены р значащими разрядами, точными будут р значащих разрядов.
Далее, до тех пор, пока можно быть уверенным, что числа не слишком велики, можно складывать, вычитать и умноззать целые числа н считать лри этом, что округление не сказывается на точности. Но предположим, что программисту необходимо определить, является ли т точно кратным л, когда лз и л ЗЗ О аба целые. Далее предположим, что в нашем распоряжении имеется подпрограмма лля вычисления величины голод(и шоб 1) = к Яз) 1 дзя любого заданного числа в в формате с плавающей точкой, как в упр.
4.2,1-15. В качестве подходящего способа определения, является ли гл кратным л, можно было бм проверить выполнение соотношения (лз З л) ([»2з) 1 = О, подразумевая наличие указанной выше подпрограммы. На, возможно, в некоторых случаях эта проверка не даст адекватного резульъъта из-за ошибок округления при выполнении вычислений в формате с плавающей точкой. Отыщите подходящие условия, которые ну,"кно наложить на диапазон значений целых чисел л з» О и зл, такие, чта т является кратным л тогда и только тогда, когда (зл З л) (н»в) 1 = О.
Другими словами, покажите, что, если зл и л не слишком велики, эта проверка дает верный результат. 14. [М87] Найдите подходящее значение г, такое, чта (и З э) З м - к З (е З ш) (с), если выполняется ненормализованное умножение. (Этим обобщается соотношение (29), посколысу ненормализованное умножение нормализованных операндов к, а н ш в точности повторяет результат нормализованного умно»кения.) ° 16. [М84] (Г. Бьерк (Н. В)бг1с).) Действительно ли вычисленная средняя точка интервала всегда находится менову крайними точками? (Другими словами, действительно лн из а < о сзедует, что и < (и Ю э) З 2 < а?) 16 [М88] (а) Чему рашю (.. ((хз З хз) Ю ха) З З хо) прн использовании восьмиразрядного представления в формате с плавающей точкой, если л = 10 н х» = 1.1111111 для любых й? (Ь) Что произойдет, если использовать выражение (14) для вычисления стандартного отклонения на множестве этик конкретных чисел х»? Что произойдет, если вместо этого выражения использовать формулы (16) и (16)? (с) Докажите, что 5» > О в (16) при любых хз, ..., х».
17. [88] Разработайте подпрограмму РСйр для Е11, сравнивающую число в формате с плавающей точкой и, которое находится по адресу 1СС, с числам в формате с плавающей точкой а, которое находится в регистре А и устанавливает в индикаторе сравнения значение ЬЕЕЕ, ЕОО11 илн ОИЕ1ТЕЕ соответственно результату и < е, к е нли и з- а (з). Здесь е хранится па адресу ЕРЕП.ОИ в виде неотрицательного значения с разделяющей тачкой, фиксированной слева ат старшего разряда слова. Предполагается, что входные значения нормализованы.
16. [М40] Существует лн в арифметике ненормализованных чисел подходящее значение з, такое,чФоиЗ(аЗш) ш(аЗо)З(иЗш) (е)? » 19. [МВВ] (У. М. Кахан.) Праанвлизнруйте сзе,зующие процедуры суммирования хм ..,,х в формате с плавающей точкой: зе = со = О; у» х»Зс» н в» = в»-з Зу», с» = (з»Зв» з)Зу», где 1 < к <и. Будем считать, что относительная ошибка в этих операциях определяется по формулам у» = (х» — с»-з)(1+ л»), ⻠—— (з»-з + у»)(1+о»), с» = ((⻠— в»-з Н1 + ?») — у»)(1 + 8»), где ]л»[,[о»],[у»[,[8»] < ь Доказките, что в„ = 2 „", (1 + В»)х», где ]В»] < 2с + О(змз).
[Теорема С угзерждвлт, что, если Ь = 2 и [з» з ] > ]у»], имеем точное равенство в» з + у» = з» вЂ” с». Но в данном упрюкнении желательно получить оценку, которая справедлива даже е шоле случае, коеда реоульшаш операции е форжаше с плаеающе6 щечкой окруаеен не очень аккуратно, при единственном предположении, что каждая операция дает ограниченную относительную ошибку.) 20. [22] (С. Линненмаа (Б.
Мвпа(шпаа).) Найдите все и н е, для которых [и[ > [О[, а соотношение (47) не вмпслняетсл. 21. [МЯЛ] (Т. Дж. Деккер (Т. 3. беккет).) Теорема С показывает, как выпоанить "точное" сложение чисел в формате с плавающей точкой. Покажите, кшс выполнить "то юноел умножение чисел в формате с плавающей точкой: выразите произведение ис в форме 1о+ ю', где 1о и ю' вычислены на основе заданных чисел в формате с плавающей точкой и и е с использованием только операций Ю, В и З. 22. [М80] Может ли возникнуть дрейф при умножении н/или делении в формате с плаваЮщвй тОЧКОйу РаССМОтрИтЕ ПОСЛЕдааатЕЛЬНОСтЬ ХО = и, Хза+1 = Хз З О, ХТ ТЭ = ХЬ Н ЗЕ при заданных и и е;Е О, Каково значение наибольшего индекса к, при котором возможно выполнение ушювия хь эе хеаэ7 ь 23. [М22] Докажите или опровергните следующее утверждение: для всех чисел и в формате с плавающей точкой справедливо равенство и З (и (иае) 1) = [и].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
