AOP_Tom2 (1021737), страница 186
Текст из файла (страница 186)
Доказательство будет завершено, если показать, что Ьг'г1т'(/ +/, ) 6г~з '(/ +6 " ~г,.). Из предыдущего абзаца имеем Ьгэ~(/„+ /„) Ь" э~/„+ Р'„= Ьг+~(/„+ 6 " ~Г„.), из чего глелует искомый рсзультат для всех ) < 1. Аналогичное замечание справедливо и в отношении шага М2 алгоритма М. Обратите внимание, что, когда Ь > 2 четное, такое целое число Г„существует всегда; но если Ь = 2, потребуется р + 3 бит (полагаем 2рг целым). Если 6 нечетно, то целое Ре существует всегда, кроме случая деления в алгоритме М, когда возможен остаток —.,Ь 1 б. (Рассмотрите г О чай, когда е„= е„, /„= -/„, в программе А.) Регистр А сохранит предыдущее значение знака, как и при выполнении команды АОО. 7.
Будем говорить, что число нормализовано тогда и только тогда, когда оно равно нулю или его дробная часть находится в диапазоне — < ~/~ < 1. Аккумулятор па 1 1 (р+ 1) разрядов вполне подойдет для операций сложения и вычитании; округление (кроме случая деления) эквивалентно отбрасыванию лишних разрядов. Кажется, получилась очень привлекательная система! Можно использовать представление чисел порядком с избытком нуль, вставленным между первым и последующими разрядами дробной части и дополненным, если дробная часть отрицательна. Так что сохраняется порядок, принятый для чисел с фиксированной точкой. 8. (а) (06, 4.12345679) 6) (06, †.12345678), (01, +.10345678) 61 (00, †.94000000); (Ь) (99, +.87654321) 1л оно же, (99, +.99999999) Э (91, +.50000000).
9. а = с = (-50, +.10000000), 6 = (-41, +.20000000), 11 = (-41, +.80000000), У = (11, +.10000000). 10 (50, +.99999000) с1(55, + 99999000) 11. (50, +.10000001) З (50, +.99999990). 12. Если 0 < !/„/ < //,./, то )/„( < )/,! — Ь г; следовательно, 1/Ь < (/„//,) < 1 — Ь г/ц„/ < 1 — 6 г.
Ег1и 0 < //„) < !/ ~, имеем 1/Ь < )/ //,!/Ь < ((1 — Ь е)/(1/6))/Ь = 1 — Ь ~. 13. См. д. М)сЛае) Тойе, 1ЕЕЕ Т) апзасбопз С-22 (1973), 577-586, а также упр. 4.2.2-24. 14. Р1Х 57) 9Р Подпрограмма ПТ-в-1РТ. ЕТА ТЕМР 1))1 ТЕИР(ЕХР) гП 1 в е. ЕАА 1 гА е- ~////О. Нуль на входе? 3АХ ЯР ОЕС1 1 СМРА 0 (1:1) 3Е в-4 ЕММ1 "О"4,1 31М РХХОЧРЬО ЕИТХ 0 ЯНАХ 0,1 СИРХ 1//2 9Р ЛО в+2 3АО 9Г Если ведущий байт равен нулю, снова сместить влево.
Абсолютное значение слишком велико? В некоторых случаях становится нечетным, поскольку 6/2 четно. При необходимости округлить. А»!»! х ! (переполнение невозможно). Выход из подпрограммы. $ ЯТА Э+1(0:О) 1ИСА 1 9Н 3МР гА +- /,. г!2» — е„. Удалить целую часть и. Дробная часть отрицательна: найти ее дополнение. Размер слова минус единица 3 16. Если )с~ > )Н), то установить 㻠— »?Зс, в»-се»(гЗ»?); х» — (аб)(ЬЗг))Зв, у»-(Ь 9 (о З г)) З в. В противном случае установить г » — с З »?, в +- »? й» (г З с); х » — ((а З г) »Э Ь) З в, М »- ((6 З г) »9 а) З в.
Тогда х + !9 есть искомая аппроксимации (а + 6»)/(с + аН). [САСАХ 5 (!963), 435. Другие алгоритмы Лля выполнении арифметических операций с комплексными числами и вычисления соответствующих функций описаны в работе Р. 1чупп, В1Т 2 (1962), 232 — 255; см, также Рао! Рйед!апб, САСА4 10 (1967), 665.) 15. РР ЯТ) )ОЧ ЯТА ЕИТХ ЯЬА 102 ОЕС2 32ИР ЯЬА ЕМТ2 ЛАММ ЕИИ2 ЯНАХ ЕМТ2 ЛХМХ 312 1МСА АОЮ 1Н 1МС2 3МР ВН ЕОО ММ1 СОИ ЕХ1ТР ОРЬО ТЕМР 0 1 ТЕМР(ЕХР) О в+3 0,2 0 1Р 0,2 0,2 0 в+3 ° +2 1 ЧМ1 О МОНН 1(1:1) ВВ-1,88-1(1:4) Подпрограмма для выделения дробной части. Снятие блокировки переполнения.
ТЕМР »- о. Добавить размер слова минус единица. Подготовка к нормализации результата. Нормализовать, округлить и выйти из подпрограммы. 17. (См. ВоЬегс Могпэ, 1ЕЕЕ Тгаоэасг1ооя С-20 (1971), 1578-1579.) Для такой системы анализ ошибки более сложен, поскольку здесь предпочтитедьнее использовать арифметику интервалов.
18. Для положительных чисел решение таково. Сдвигать дробную часть влево до тех пор, пока не окажется, что ~~ = 1; затем округлить, затем, если дробная часть равна нулю (переполнение при округлении), снова сдвинуть вправо. Для отрицательных чисел решение таково. Сдвигать дробную часть влево до тех пор, пока не окажется, что ~~ = О; затем округлить, затем, если дробная часть равна нулю (исчезновение значимости при округлении), снова сдвинуть вправо. 19. (43 + [е < е ] — [переполнение дробной части] — 10[результат — нуль] + 4[абсолютная величина округлена до] 4 [первый округленный разряд равен 6]+ 5 [округленные разряды ь 2 равны 90.,.
О] + 7 [переполнение при округлении]+ 7Х+ (11 ( !У >0] — 1) [гХ принимает ненулевые разряды])в, где А' есть число сдвигов влево при нормализации. Максимальное время 73в получается, если, например, и = .ь50 01 00 00 ОО, е = -4б 49 99 99 99, Ь = 100. (Учитывая данные из раздела 4.2 4, время будет иметь порядок 45.5и.] Р)ВЗДЕЛ 4.2.2 1. о Е о = в В -о = -е В и = — (о б! — в) = — (е Е в). 2. вб!х > об!О = и, как следует из (8), (2), (б), поэтому сновав силу (8) (иЫх)Яо > вЮш Аналогично из (8) и (б) вместе с (2) следует, что (в О! х) я (о б! 9) > (о Я х) З ш 3.
и = 8.0000001, о = 1.2500008, ш = 8.0000008; (в З е) З ю = 80.000004, и З (о З ю) = 80.000057. 4. Да,:пусть 1[и е = ю, где е велико. 5. Не всегда, им~ример для чисел и = е = 9 в десятичной систелге, б. (а) Да. (6) Только для 6+р < 4 (попробуйте проверить с в = 1 — Ь г). Но см. упр. 27. 7. Если и и е — последовательные числа с плавающей точкой, о Ю е = 2в или 2е.
Когда это 2е, мы часто получаем и(Э ~ еО' < 2еО', Например, в = (.10... 001)ю е = (.10... 010) м в бз е = 2о и и(1) + ей = (.10... 011)м 8. (а),; (Ь), щ; (с),; (д); (е) 9. [и-ю[ < [и — е[+]е-ю[ < г~ ш!п(6'" ', Ь'" ']+сею!о(Ь'" е,Ь'" е) < с~Ь'" е+еэЬ'" (еь + ет) щах(6'" е,Ь' е). В общем случае усилить этот результат нельзя. Например, можно было бы взять е„очень малым по сравнению с обоими порядками е„и еь, но зто означало бы, что и — ю слишком велико при сделанных предположениях. 10. Если ар > 1 и а~ > 1, получим (.а~ ..ар ~ар)ь З (.9..
99)ь = (а~ ар-~(ар — 1))ь; здесь "9" есть 6 — 1. Далее, (аю,.аг ~ар)ь З (10... 0)ь = (ою ..ар ~0)ь, так что, если 6 > 2 и аг > 1+ [о~ > 1], умножение оказывается не монотонной операцией. Но в случае, когда Ь = 2, игпользуя то же самое рассуждение, можно доказать, что умножение является монотонным. Очевидно, "некий компьютер" имеет Ь > 2. 11.
Можно положить без ущерба для общности рассуждений, что т есть целое, 0 < х < Ь". Если е < О, то! = О. Если 0 < е < р, то х-!имеет не более р+1 разрядов, причем наименее значимый равен нулю. Если е > р, то х — 1 = О. [Результат справедлив и при более слабой исходной посылке [1[ < Ь', в этом случае можно было бы получить х — 1 = Ь', если е > р.] 12. Предположим, что е = р, е, < О, в > О. Случай 1: а > Ьг '. Случай (1, а): ю = в+1, е > —,', е„= О.
Тогда и' = и или о+ 1, е' = 1, и" = в, е" = 1 или О. Случай (1, Ь): ю = и, [е[ < -'. Тогда и' = и, е' = О, иа = и, еа = О. Если [е[ = -' и допустимо более общее правило округления, можно было бы получить и' = и х 1, е" = ~1. Случай (1, с): и = и — 1 е < — -', е., = О. Тогда и' = и или и — 1, в' = -1 иа ы и, ео = — 1 или О. Случай 2: и = Ьд . Случай (2, а): те = и+ 1, е > -', е, = О, как в (1, а). Случай (2, Ь): ит = и, [е[ < -', и' > и, как в (1, Ь). Случай (2, с): ю = и, [е[ < -', и' < и.
Тогда и' = и — 2/Ь, где в = //Ь+ е~ и [от[ < -'Ь ' для некоторого положительного целого / < -'Ь; имеем е' = О, ие = и, еа = //Ь, Случай (2, т1): ю < и. Тогда ю = и — //Ь, где е = — //Ь+ е~ и [от[ < тЬ ' для некоторого положительного целого / < Ь; имеем (е',и") = (-//6,и) и (й,ев) = (и, -//Ь) или (и — 1/Ь, (1 —,у)/Ь); последний вариант возможен, только если ет — — -6 . В любом случае и О и' = и — й, е Ю е' = е — в', и О ио = и — и", в 9 е" = е — е", т -1 т гоипт((ю — и — е) = ю — и — е.
13. Поскольку гонят)(х) = 0 тогда и только тогда, когда х = О, нужно найти множество пар целых чисел (тп, и), обладающих таким свойством: результат ш О и есть пелое число тогда и только тогда, когда целым числом является тп/~. Предттоложнмгчто (пт[, [и[ < Ьд, Если тп/и есть целое, то тп Оп = тп/~ — также целое. И наоборот, если тп/и не есть целое, а тп О и — целое, имеем 1/[и[ < [тп О и — тп|п[ < 1[то/п[6' ". Следовательно, [тп[ > 26д Значит, ответ таков: нужно потребовать, чтобы выполнялись условия [тп[ < 2Ьд ' и О < [и( < Ьд. (Возможно и чуть менее жесткое ограничение.) 14.
[(иЗе)Зте — иею[ < [(иЗе) Зет — (иЗе)ю[+)те)[иЗе-ие[ < бтднши,„+Ь'" д ~ Ь„нт < (1+ Ь)5ыишх . Теперь [еынши — едят„и 1[ < 2; таким образом, в качестве искомого результата можно взять е = -'(1 + Ь) 6' ", 15. Из и < е следует, что (и О и) О 2 < (и Ю е) О 2 < (е Ю е) О 2. Таким образом, сформулированное в задаче условие остается справедливым для любых и и е тогда и только тогда, когда оно справедливо для любых и = е. Для основания 6 = 2 исходное угловие справедливо всегда (за исключение случая, когда возникает переполнение); но при 6 > 2 существуют числа е ф ет, такие, что е З е = ю Ю та.
Значит, сформулированное в задаче условие не выполняется. [С другой стороны, формула ибд ((е О и) О 2) действительно дает среднюю точку, лежащую внутри интервала. Докаэатпельсшеа. Достаточно показать, что и+ (в Э и) О 2 < е, т. е. (е 9 и) О 2 < в — и; легко проверить, что гонят((-'говпт1(х)) < х для любых х > О.[ 10. (а) Изменение порядка появится в суммах А„та — — 11.111111, 2 д, = 101.11111, 2 1001.1102, х доп = 10001.020, 2;досад = 100000.91, г„,'даадтд — — 1000000.0; таким образом, х тоооаоа = 1109099.1. (Ь) После определения султмы ) „", 1.2345579 = 1224782.1 вычисления в соответствии с (14) приведут к попытке определить квадратный корень из —.0053187053.
Но в этом случае вычисления в соответствии с (15) и (1б) будут точными. [Если хд = 1 + [(Ь вЂ” 1)/2) 10 т, то вычисления в соответствии с (15) и (15) дадут ошибку порядка и. Более детальный анализ точности вычисления стандартного отклонения приведен в работе СЬап апт1 Ьекчд, САСМ 22 (1979), 52б-531.] (с) Нужно показать, что и Ю ((в О и) О Ь) находится между и н е; см. упр.
15. 17. ГСМР ЯТЛ 9Р Подпрограмма для сравнения чисел в формате с плавающей точкой. ЛОТ ОРЬО Убедиться, что индикатор переполнения выключен. ЯТА ТЕМР ЬЯАМ ТЕМР е т- -е. (Сюда скопируйте строки 07-20 из программы 4.2.1А.) 603 РЧ(0:0) Присвоить гХ значение "нуль" со знаком, совпадающим со знаком /„. ОЕС1 5 ЛХИ э+2 ЕНТ1 О ВВЛХ 5,1 ЛОО Г0 10ч 7Г СИРЛ ЕР51ЕОИ(1у5) 60 ВГ 11 ВГ 112 9Г 6ХР 1Г 6ЛР 9Г 3ИР ВГ 7Н ЕИТХ 1 ВНС 1 6ИР ВГ 18 1ЛР ВГ ВН ЕИТЛ 0 ВН СИРЛ =0 9Н 6НР Заменить большое значение разности порядков меньшим. гА е- разность операндов. Переполнение при вычислении дробной части: не Переход, если нет Переход, если Переход, если Если )гА) = е, проверить знак гА х гХ Переход, если (гА ,-6 О).
Установить в гА ненулевое значение с тем же значением. Переход, если не (гА эб О). Установить индикатор сравнения. Выход из подпрограммы. $ 19. Пусть Ть = бь = Вь = аь = 0 при ус > и. Достаточно найти коэффициент прн хи поскольку коэффициент при гь будет точно таким же, если все индексы увеличить на Л вЂ” 1. Пусть (уь,дь) означают соответственно коэффициенты при ху в (эь — сь,сь). Тогда ~у = (1+ уууИ1 — Ту — Т~бу — Туа~ — буау — Тубуау), ду = (1+ бу)(1 + ууу)(7~ + ау + Туау) и уь = (1 — Тьаь — бэаь — Тьбьаь)уь у + (Ть — ууь + Тьбь + Тьць + тьбьууь + Ть0ьаь+ бьОьаь + ьбьтуьаь)дь и дь = аь(1-~-зь)(14-бз)~ь у — (1+ бь)(уь+.уьОЛ + ууьаь + Тьууьаь)дь и где 1 < й < и, Тогда 1'„= 1 + ууу — уу + (4п членов второго порядка) + (члены более высоких порядков) = 1+ уу~ — Ту + 0(пе~) будет достаточно малб.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
