AOP_Tom2 (1021737), страница 187
Текст из файла (страница 187)
(Формула суммирования Кахана впервые была опубликована в САСМ 8 (1965), 40; см. также Ргос. 1РХР Солдгеьэ (1971), 2, 1232, а продолжение — в работе К. Стана, у 1пйиша1юп Ргос. 6 (1983), 226 — 230. Другой подход к организации точного суммирования описан в работе Н, 6. Напэоп, САСМ 18 (1975), 57. 58. Когда одни хь отрицательны, а другие положительны, можно с пользой для дела скомбинировать их, как рекомендуется в работе Т.
О. Еэре(Ы, ЯАМ Яегуеи 37 (1995), 603.607. См. также работу С. ВоЫепбег, 1ЕЕЕ Тгалэ. С-26 (1977), 621 — 632, где приводятся алгоритмы, которые вычисляют гоипб(ху + + х„) и гоипб(ху... х ) точно, по заданным (гм.,, х ) у 20. Как следует из доказательства теоремы С, соотношение (47) не выполняется при е = р, только если )и) + -' > )ус — ю) > Ь" '+ Ь ', поэтому )уь) > )~~) > 1 — (-,'Ь вЂ” 1)Ь ~. Теперь приходим к выводу, что необходимое и достаточное условие "невыполнения" (47) есть округление )1 ), по сути, почти до 2 в процессе нормализации (фактически до 2/Ь после масштабирования посредством сдвига вправо для получения переполнения дробной части).
Случай, конечно же, чрезвычайно редкий! 21. (Решение Г. В. Вельткампа (С. Ж. Ъе(г(шупр).) Пусть с = 2уэу~у + 1; можно предположить, что р > 2, так что с репрезентативно. Сначала вычислим и' = и З с, иу =(ийй)буи', из =айны аналогичное =иЗс, иу =(ифи')Эи,иэ =иЭиь Затем присвоим ю +- и З и, ус е — (((щ З ю З и') Ву (иу З иэ)) бу (иг З иу)) иу (иэ З из). ДОСтатОЧНО дОКаэатЬ Эта дЛя СЛуЧая, КОГда и, и > 0 И Еь ж Е„= р, таК Чта и И и ЕетЬ целые б [2г ~ .. 2г). Тогда и = и~ -Ь ию где 2г ' < иу < 2", иу глоб 2угу~у = 0 и )иэ~ < 21ешУ ', аналогично и = су + ию Операции, выполняемые при вычислении й, являются точными, поскольку ю — и~»~ кратно 2г ', причем [и — н~»~[ < [ю-н»[+[из»~+а~ »с+из»з[ < 2» '+ 2г+1"7з1+ 2" ', аналогично [ю — и~»~ — н~»з[ < [ш — и»[+ [кз»[ < 2г '+ 200Ы ьь", где ю — в~»~ — в~»з кратно 2 1г/з1 22.
Можно предположить, что Ьг ' < и, » < Ьг Если в» < 6гя ', то х~ = и» вЂ” г, где (г[ < -'Ь" '. Значит, хз — — говно(в — г/») = х (в1псе [г/»[ < -'Ьг '/Ь" < -' и при равенстве следует» = Ь" ', откуда г = О). Если и» > Ь'г ', то х~ — — и» вЂ” г, где [г[ < -'Ье. Позтому х~/» = и — г/» < 6" + -'Ь и хз < Ь". Если хз = Ьг, то хз = х~ (поскольку из условии (6~ — —.')» < х~ следует что х~ кратно Ь и имеем х~ < 6г(»+ з)). Если хз < Ь~ и х~ > Ь~г то пусть хз = хг/»+ д, где [д[ < -'; получим хз = гоппб(х~ + д») = хь Окончательно, если хз < Ьг, х~ = Ь~г ' и хз < 6гв ', то хз = хз как следствие первого из рассмотренных выше случаев.
Такая ситуация может возникнуть, например, когда 6 = 10, р = 2, и = 19, » = 55, хь = 1000, хз = 18, хз = 990. 23. Если и > 0 или и < — 1, имеем и ~~ьоь) 1 = кшоб 1, так что равенство справедливо. Если -1 < и < О, то н Я е 1 = н ш 1 = и + 1 + г, где [г[ < -'Ь г; равенство справедливо тогда и только тогда, когда гоппд(1 + г) = 1, так что оно будет иметь место всегда, когда выполняется округление до четного. Если использовать правило округления, приведенное в тексте раздела, то равенство не будет выполняться тогда и только тогда, когда Ь кратно 4, — 1 < в < 0 и и шод 26 ~ = зЬ " (например, р = 3, 6 = 8, и = -(.0134)з).
24. Пусть и = [тч .. в ], » = (»~ .. »,]. Когда и Ю» = (ш чг»~ .. в, Й»,], где х Й у = д Й х, х Й +О = х длн всех х, х Й вЂ” 0 = х для всех х ~ +О, х Й +со = +ос для всех х ф -оо, а х Й -со не нуждается в определении; х зу д = -(( — х) Й (-у)), если х В д приведет к переполнению при выполнении операции согласно обычным алгоритмам работы в формате с плавающей точкой, поскольку х + д слишком велико, то х Й у есть +ос и х ~Е у является наибольшим по величине представимым числом. Для вычитания положим в О» = и Оз ( — »), где -» = (-», -»~].
С умножением дела обстоят сложнее. Правильный результат даст такая процедура: пусть и ез»= [ш1п(и~ '(у»п и~ ~ф' »„, и, "зу»п в, 3у»,) . шак(в~ Й»п ш Й»,, в,. Й»п и, Й», )], гдехйу = дйх, хЙ(-д) = -(хб'д) = (-х)Йу:, хЙ+О = (+О прях > О, — 0 при х < 0); х Й вЂ” 0 = — (х Й+О); х Й+оо = (+со при х > +О, — оа при х < -0). (Можно определить минимум и максимум, просто просмотрев знаки нп н,, »~ и»„и вычислив таким образом только два нз восьми произведений, кроме ситуации, когда»з < О < в, и »~ < 0 <»; в последнем случае нужно вычислить четыре произведении и результатом будет (пцп(щ 37»„, в„'Ьг»~) ..
шак(щ Й»пи, Й»,.)[.) Окончательно получаем: в;с» неопределенно, если ш < 0 <»„; иначе — будем использовать форгяулы длн умножения, заменив»~ и», соответственно значениями», ' и»,~,гдехйд ~=хЙд,х дд ~=х~(уу,(+Л)) ~=хо»,(хоо) ~4 60. [См. Е. Н. Наивен, Маей. Сотр. 22 (1988), 374 — 384. Альтернативная схема, в которой деление на 0 не приводит к сообщению об ошибке и интервалы могут быть окрестностими ос, предложена У. М. Квханом (%'. М. Кабан). Ио схеме Казана, например, обращение [ — 1 .. +Ц дает результат [+1 . -1], а попытка умножения интервала, включающего О, на интервал, включающий оо, дает результат [-со ..
+со], т, е. множество всех чисел. Сл». Хителса7 Апа1уяв, 1 пис М1с618ал Епййпесйпй Бппппег Сопб удогез Хо. 5818 (1908).] 25. Это явление связано с ошибками в предшесшедю»1их операциях вычисления и и». Например, если е мало, /(х+ е) 9 /(х) часто вычисляется с низкой точностью, поскольку округление при вычислении /(х + е) приводит к утрате информации об е. Рекомендуется переписать эту формулу в виде г З д(х, е), где д(х,г) = (/(х + е) — /(х))/е определяется сначала в символьном виде.
Таким образом, если /(х) = хз, то д(х,е) = 2х+ е; если /(х) = з/х, то д(с~ е) = 1/(~/х + е +»'х ). 20. Пусть е = шах(е„, е„), е' = шах(е„, е„), е» = шах(е„в„, е„в, ), и предположим, что 9 = О. 'Тогда (ив» о) — (и' ч» с') < и+ о+ -'Ь' " — и' — о'+ 26' г < 46'+ еЬ' + Ь' г и е" > пэах(е,е'). Следовательно, и 19 о и' Ые' (24+ 6»). Если 6 = 2, зта оценка может быть уточнена до 1.54 + 6 г. При условии, что 4 + 6 есть верхняя граница, если и — и' и э — о~, получим противоположные знаки, а в другом случае не может оказаться е = е' = е".
27. Сформулированное тождество есть следствие того, что 1З(1йи) = и при Ь ' < / < 6 '2~. Если последнее ложно, значит, могут существовать целые числа х и у, такие, что Ь" ' < х < Ь" М', и либо у — 2- < 622 '/х < Ьэ" '/(х — 2 ) < у, либо у < 62» '/(х + 2) < 62" '/х < у+ 2. Но последнее явно невозможно, если только не выполняется соотношение х(х + -') > Ьэе ', а это последнее условие влечет за собой у = (Ьг Ы2) = х. 28. См. МайЛ. Солце.
32 (1978), 227-232. 29. Когда 6 = 2, р = 1 и х > О, имеем топай)(х) = 2м ~, где г(х) = (18-'х). Пусть /(х) = х и пусть 2(п) = ( оп+18 1)/а+18 ф). Тогда й(2 ) = 2цы. Когда а =.99, получим Й(2') = 2' ' для 41 < е < 58. 31. Как следует из теории, которая будет изложена в разделе 4.5.3, »сходимость» бесконечной дроби эйгЗ = 1+ //1,2, 1,2,... // есть р„/д„= К е2(1, 1,2, 1, 2,... )/К (1,2, 1,2,...). ЭтО ПРЕКраеиая аППрОКСИМацИя дпя 2/3, ПОСКОЛЬКУ Зд» яе Р„, а фаКтИЧЕСКИ Зׄ— р» ж 2 2 2 — 3(п шой) 2). Заданный в условии пример таков: 2Р22+ (Зузй — Рзй)(3922 +Рзй) = 2рэй — (Рэй — 1+Рай) = 1 Вычитание в формате с плавающей точкой рэ, из 3922 дает нуль, если только нельзя 2 2 представить Здэй почти точно.
Вычитание рэ, из 9922 дает в общем случае ошибку округ- 2 4 4 ленив, значительно ббльшую, чем 2рээ,. Аналогичный пример можно сформулировать, основываясь на аппроксимации бесконечной дробью любого алгебраического числа. РАЗДЕЛ 4.2.3 1. (в2,еэ) = (.573,.248); тогда юмей/ш = .290. Таким образом, результат равен (.572, .958). Он верен с точностью до шести десятичных знаков.
2. Это не окажет никакого воздействия на результат, поскольку подпрограмма нормализации обрезает до восьми разрядов и никогда не принимает в расчет байт в этой позиции. (Сдвиг влево происходит в ходе нормализации не более одного раза, так как предполагается, что входные данные уже нормализованы.) 3. При выполнении команды в строке 9 переполнение, очевидно, произойти не может, поскольку складываются двухбайтовые величины. Не может оно произойти и при выполнении команды в строке 22, так как складываются четырехбайтовые величины. Команда в строке 30 вычисляет сумму трех четырехбайтовых величии, что не может привести к переполнению.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
