Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 79
Текст из файла (страница 79)
18 би вн 9И 0801 31И еит1 ВИАХ АОО 307 СНРА 30 Л. 312 3ХР 3АР 3НР 78 Нитх вйс ЗИР 3АР нитА СИРА 3НР 5 э+2 о 5,1 Ро 7Г ЕРБХ(.ОИ(1тб) 8Р 6Р 9Р 1Р 9Р 8Р 1 1 ВР ВР о о- Заменить большое значение разности порядков меньшим. гА <- разность операндов. Переполнение при вычислении дробной части: не Переход, если нет Переход, если Переход, если Если )гА) = е, проверить знак гА х гХ Переход, если (гА уА О), Установить в гА ненулевое значение с тем же значением. Переход, если не (гА уь О). Установить индикатор сравнения.
Выход из подпрограммы. 5 19 Пусть уь = 6ь = О» = еь = О при Ь > и. Достаточно найти коэффициент прк ям поскольку коэффициент при хг будет точно таким же, если все индексы увеличить на й-1. Пусть (Д,рь) означают соответственно коэффициенты при хт в (еь — сь,сь). Тогда Л = (1+ гПИ1 — 7т — утбт — Зтет — 6тет — "ут6тет), Рт = (1+ 6г)(1+ ОтН ут + а1+ учет) и ~ь = (1 — уэеь — 6ьеь — Эьбьеь)~ь 1 + (уь — бэ + 7ьбь + уьОэ + ть6ьиь + уьОэеэ + 6ьОьеь + 7ь6ьтуьеь)иг-и оь = еь(1+ зьЦ1+ 6ь)Д-т — (1+ 6ь)(уь + уьОь+ Оэеь + уьтуэоь)рь м где 1 < Й < и. Тогда Г = 1+ тут — 'уг + (4п членов второго порядка) + (члены более высоких порядков) = 1 + тут — пт + О(не ) будет достаточно малб, (Формула суммирования Каана впервые была опубликована в САСМ 8 (1965)., 40; см.
также Ргос. ХР1Р Сопвтвш (1971), 2, 1232, а продолжение — в работе К. Озава, Х улуогшабоп Ргос. 6 (1983), 226-230. Другой подход к организации точного суммирования описан в работе К. 3. Напвоп, СЛСМ 18 (1975), 57 — 58. Когда одни хь отрицательны, а другие положительны, можно с пользой для дела скомбинировать их, как рекомендуется в работе Т. О. Езре!Ы, ЯАМ Еле(ете 37 (1995), 603-607. См. также работу О. ВоЫепбег, ЕЕЕЕ 2?апз. С-26 (1977), 621-632, где приводятся алгоритмы, которые вычисляют гошин(гт +...
+ я„) и гошк((гт... хь) таочао, по заданным (хм, .., х„).) 20. Как следует из доказательства теоремы С, соотношение (47) не выполняется при е,. = р, только если )е) + - > )ет — а! > Ь" + Ь, поэтому Щ > )~т! > 1 — (-Ь вЂ” 1)Ь т, Теперь приходим к выводу, что необходимое и достаточное условие "невыполнения" (47) есть округление ф„(, по сути, почти до 2 в процессе нормализации (фактически до 2уЬ после масштабирования посредством сдвига вправо для получения переполнения дробной части). Случай, конечно же, чрезвычайно редкий! 21. (Решение Г, В.
Вельткампа (О. %. Че(гйтппр).) Пусть с = 2утдо + 1; можно предположить, что р > 2, так что с репрезентативно. Сначала вычислим й = а З с, ит = (аОа ) 6Уи, ат = афти; аналогично е' = еЗс, ет = (еОе') 9е', ез = а Зем Затем присвоим ш Ф- а З е, е/ Ф- (((ат З е! гт ш) ат (ит З ет)) бт (ит З ш)) бу (ат З ет). Достаточно доказать это для случая, когда и, е > 0 и е„= е„= р, так что и и е есть целые 6 (2г ' .,2т), Тогда и = иг + им где 2т ' < и1 < 2т, ит шод 2утдб = 0 и 1аэ! < 2(тдб '; аналогично е а ет + еэ. Операции, выполняемые при вычислении те', являются точнымн, поскольку з»-азиз кратно 2» ', причем [ы-изез] < [з» вЂ” ив[+[изе1+и|ез+изез[ < 2» ' + 2»+1»гз1 + 2» ', аналогично [з» вЂ” а1»1 — аз ез] < [з» вЂ” ив] + ]из»[ ( 2г ' + 2 Гг~з1 где з» вЂ” азвз — извз кратно 2~»~ 1.
1»Гз1 22. Можно предположить, что Ьз ' < и,в ( 6". Если ае < Ьз" ', то хз = ие — г, где ]г] < -'Ьг з, Значит, за = гоапб(а-г/е) = хо (япсе ]г/е] < -'Ь" '/Ьг ' ( -„' и при равенстве следует е = Ь' ', откуда г = О). Если ав > Ьз' ', то хз = ив — г, где [г[ < 1Ь». Поэтому хз/е = и — г/е ( Ьг + -'Ь и хз < Ьг. Если хз ж Ь", то хз = хз (поскольку нз условия (Ь" — -')е ( х, следует, что хз кратно 6» и имеем хз < Ьз(е+-')).
Если хз < Ьг и хз > 6з" ', то пусть хз = х1/» + д, где ]д[ < -'; получим хз = гоипб(хз + дв) = хь Окончательно, если хз < 6", х1 ж Ьзг ' и хз < Ьзг ', то хз = хз как следствие первого из рассмотренных выше случаев. Такая ситуация может возникнуть, например, когда Ь = 10, р = 2, и = 19, в 56, х1 = 1000, хз = 18, хз = 990. 23. Если а > 0 нли а < -1, имеем и (тза) 1 = и шоз) 1, так что равенство справедливо. Если -1 < и < О, то и Саззз 1 = и Ж 1 = а+ 1 + г, где ]г[ < -'6 г; равенство справедливо то~да и только тогда, когда гоппб(1 + г) = 1, так что оно будет иметь место всегда, когда выполняется округление до четного.
Если использовать правило округления, приведенное в тексте раздела, то равенство не будет выполняться тогда и только тогда, когда Ь кратно 4, — 1 < а < 0 и а шоб 26 г = зЬ " (например, р = 3, Ь ж 8, а а -( 0134)з). 24. Пусть и = ]щ, . и ], в = ]в~ .. е,], Когда и Ю е = [и~ З(у щ, . и й в„], где х й д = д й х, х Й+О = х для всех х, х Й вЂ” О = х для всех х 16 +О, х Й +ос = +ос для всех х ~ -оо, а х й — оо не нуждается в определении; х зд д = -((-х) Й (-д)). Если х 19 у приведет к переполнению при выполнении операции согласно обычным алгоритмам работы в формате с плавающей точкой, поскольку х + д слишком велико, то х Й д есть +ос н х 'у у является наибольшим по величине представимым числом.
Для вычитания положим и 19» = иЮ( — в), где -в = [-», -в~]. С умножекием дела обстоят сложнее. Правильный результат даст такая процедура: пусть а 8 »=]ш1п(а~ з)г зз,тц 'ф'в„а,~ ш, и,з)7 в,) ., шах(зз Й вн щ Й в„и, Й »пи, Й е„)], глехйд = дйх, хй(-д) = — (х~Рд) = (-х)йд; хй+О = (+Опрнх > О, -О при х < 0); х Й вЂ” 0 = — (х Й+0); х Й+оо = (+ос прн х > +О, — оз при х < -0). (Можно определить минимум и максимум, просто просмотрев знаки щ, и„в~ н е„и вычислив таким образом только два нз восьми произведений, кроме ситуации, когда щ < 0 < и, и зз < 0 < е„в последнем случае нужно вычислить четыре произведения н результатом будет ]ппп(щ 'Е е,. и„Зу щ) ..
шах(и~ Й в~ а, Й е )] ) Окончательно получаем: и»з в неопределенно, если щ < 0 < в„; иначе — будем использовать формулы для умножения, заменив в~ и в„соответственно значениями е, ' ие,',гдехйд '=хйд,хазу '=хз(зд,(жО) 1=кос,(хсо) '=х0. [См. Е. К. Напзеп, Маей. Сошр. 22 (1988), 374-384. Альтернативная схема, в которой деление на 0 не приводит к сообщению об ошибке н интервалы могут быть окрестностями оо, предложена У.
М. Каханом (%. 61. Кабап). По схеме Кахана, например, обращение [ — 1 .. +1] дает результат ]+1,. -1], а попытка умножения интервала, включающего О, на интервал, включающий оо, дает результат [ — со., +ж], т. е. множество всех чисел. См. Хаше»1»а) Апа)узЫ, Пшг. МкЬ!8ап Епб)пеегшб Бипппег Сопз. Хозез Хо, б818 (19б8).] 23.
Это явление связано г ошибками в нредшссшедзощах операциях вычисления и и е. Например, если з малб, /(х+ с) и /(х) часто вычисляется с низкой точностью, поскольку округление при вычислении /(х + з) приводит к утрате информации об з. Рекомендуется переписать эту формулу в виде з аз д(х,з), где д(х,з) = (/(х+ е) — /(х))/е определяется сначала в символьном виде. Таким образом, если /(х) = хз, то д(х,е) = 2х+ з; если /(х) з/х, то д(х,г) = 1/(зЯ+е+ з/х). 28. Пусть е = швх(е„е„), е' = шах(е„е, ), е" = шех(е„еюе„е, ), и предположим, что д = О, 'Тогда (и Ф е) — (и' Ю е') < и+ в+ 1Ь' " — и' — е'+ 16' г < еЬ' + еЬ' + Ь' " и е" > шах(е, е'). Следовательно, в Ж е в' се е' (2е + Ь г). Если 6 = 2, зта оценка может быть уточнена до 1.5» + Ь ".
При условии, что е + Ь " есть верхняя граница, если и — в' и е — е', получим противоположные знаки, а в другом случае не может оказаться е = е' = е . 27. Сформулированное тождество есть следствие того, что 1 З (1 З в) = и при Ь 1 < / < Ь, Если последнее ложно, значит, могут существовать целые числа х и Р, такие, что 1/2 Ь" ' < х < Ь" ы', и либо у — 1 < Ьтг '/х < Ьег '/(х — 1) < р, либо Р < 6зе /(х+ -') < Ьге '/х < р+ 1. Но последнее явно невозможно, если только яе выполняется соотношение х(х+ -') > Ьее ', а зто последнее условие влечет за собой р = (Ьг Ыз) = х.
28. См. МвхЬ. Сошр, 32 (1978), 227-232. 29. Когда Ь 2, р м 1 и х > О, имеем гопш1(х) = 2М*~, где е(х) = 1)81~к). Пусть /(х) = х и пусть1(п) = ц(оя+)8 цп+18 ц. Тогда й(2 ) = 2цм. Когда и =.99, получим Ь(2)=2' 'для41<е<58. 31. Как следует из теории, которая будет изложена в разделе 4.5.3, "сходимость" бесконечиойдроби Яж1+//1,2,1,2,... //есть р /д = Кьы(1,1,2,1,2,...)/К„(1,2,1,2,...). Это прекрасная аппроксимация для 1/3, поскольку Зд~ ш р~, а фактически Зд~ — р~ 2 — З(п шоб 2).
Заданный в условии пример таков: 2рз1 + (Здап — рз1)(Здесь~ + рвы) = 2р~з1 — (рз| — 1+ рз1) = 1 Вычитание в формате с плавающей точкой рзз, из Здзз, дает нуль, если только иельзя представить Зды почти точно. Вычитание рз, из 9дз1 дает в общем случае ошибку округ- 3 4 4 ленив, значительно ббльшую, чем 2РЦ. Аналогичный пример можно сформулировать, основываясь иа аппроксимации бесконечной'дробью любого алгебраического числа.
МЗДЕЛ 8.2.З 1. (ш,„,ш~) = (,573,.248); тогда ш е~/е,„= .290. Таким обрезом, результат равен (.572, .958). Он верен с точностью до шести десятичных знаков. 2. Это не окажет никакого воздействия на результат, поскольку подпрограмма нормализации обрезает до восьми разрядов и иикогда не принимает в расчет байт в втой позиции.
(Сдвиг влево происходит в ходе иормализации не более одного раза, так как предполагается, что входные да~яме уже нормализованы.) 3. При выполнении комацпы в строке 9 переполнение, очевидно, произойти не может, поскольку складываются двухбайтовые величины. Не может оно произойти и при выполнеиии команды в строке 22, так как складываются четырехбайтовые величины. Команда в строке ЗО вычисляет сумму трех четырехбайтовых величин, что ие может привести к переполнению.
Наконец, при выполнении команды в строке 32 переполнение невозможно, так как произведение /,/, должно быть меньше единицы. 4. Вставьте команду ь207 021.0; ЕИ71 0" междустроками03и04. Заменитестроки 21-22 иа "АОО ТЕИР(АВЗ); 1807 в+2; 1ИС1 1", а строки 28-31 на "ЗЬАХ 5; АОО ТЕИР; ЗИОд е+2; 1ИС1 1; ЕИТХ О, 1; ЗЕС 5". Таким образом, ко времеви выполнения будет добавлено пять строк кодаи только 1, 2 или 3 машинных цикла. 5. Вставьте ь207 ОРЫ" после строки Об. Замените строки 22, 31, 39 ив "ЗЕАХ 0,1", "ЗЬАХ 5", "АОО АСС" соответственно. Между строками 40 и 41 вставьте комаиды "ОЕС2 1," 1807 ОИОЕИ; 1ИС2 1; 1ИСХ 1; ЗЕС 1". (Так и подмывает удалить "ОЕС2 1" и заменить ее комаццой "372 ЕХРО", но тогда команда "1ИС2 1" может вызвать переполнение регистра г12!) Та;ким образом, программа увеличится на шесть строк; время выполнения рмеиьшитлел на Зи, если только не возникнет переполнения при работе с дробной частью.
В этом последнем случае время выполнения увеличится на Тк. Преобразование в формат с удвоенной точностью. Очистка гХ. б. ОООВХЕ БТЛ ЕХ1ТРР ЕИТХ О БТА ТЕНР 102 ТЕНР(ЕХР) 1ИС2 00-0 БТХ ЕХРО БХАХ 1 ЗНР ОИОЕН г(2 +- е. Поправка на разность юбытков. ЕХРО ~- О. Удалить порядок. Нормализовать и выйти нз подпрограммы. Преобразование в формат е однократной точностью. Убедиться, что индикатор переполнения выключен. 91ИЯ.Е БТЗ ЗОУ БТА 602 РЕС2 БЬАТ ЗНР ЕХТТР ОРЬО ТЕНР ТЕНР(ЕХРО) 00-0 2 БОЕН г12+- е.
Поправка н» разность юбытков. Удалить порядок, Нормализовать, округлить и выйти из подпрограммы. 3 7. Все три программы дают нуль в качестве результата тогда и только тогда, когда точный результат должен равняться нулю, так что ие стоит беспокоиться о нулевых знаменателях в выражениях для относительной ошибки. Наихудший случай для программы сложения действительно плох. Перейдем для наглядности к десятичным обозначениям. Если входные значения слагаемых — 1,0000000 и .99999999, то ответ будет равен Ь"г вместо Ь а. Таким образом, максимальная относительная ошибка бг равна Ь вЂ” 1, где Ь— размер байта.
Что касается умножения и деления, то моясно предполагать, что оба операнда положительны и порядки обоих операндов разны ОО, Максимальную ошибку умножения легко можно найти, проанализировав рис. 2. Если ис > 1/Ь, то 0 < ие — и З с < ЗЬ" з + (6 — 1)Ь э, так что относительная ошибка ограничена значением (6 + 2)Ь е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
