AOP_Tom2 (1021737), страница 190
Текст из файла (страница 190)
9. На шаге А2 везде заменить»6» на»6,". 10. Если поменнть местами строки 06 и 1!7. то почти всегда можно получить переполнение. При этом регистр А в ходе выполнения команды в строке 08 может иметь отрицательное значение, так что программа работать не будет. Если поменять местами строки 05 и 06, то последовательность переполнений, происходящих в ходе работы программы, будет в некоторых случаях иной, но программа даст правильный результат. 11.
Эта задача равносильна задаче лексикографического сравнения цепочек: (1) присвоить 1 г — я — 1; (Н) если и; < о, закончить с результатом [и < о); если ггг = о, и! = О, закончить с результатом (и = в); если и, = вз и 1 > О, присвоить / ь- / — 1 и повторить (8); если из > вю то закончить (и > в). Этот алгоритм оказывается довольно быстрым, так как обычно очень мала вероятность того, что 1 станет очень большим раньше, чем возникнет случай, когда и, ЭЬ в,. 12. Используем алгоритм В при и = 0 и в, = ю,.
В конце этого алгоритма появится другое "заимствование", но на этот раз им ьюжно пренебречь. 13. ВИИХ И КЛ. Т Х БТА И+И, 1 АГ ЛОТ ОРХО 1 БЬС 6 К 1ИС1 1 )ь' ИИТХ О 1 АОО САБИТ !У 318 28 !д 28 БТХ САБИТ !д ЛИОЧ ь+2 Ж БТХ И+И 1 ЬОА О+6.1 Ж ТИСХ 1 К Время выполнения программы равно 237ь' + К + 5 циклам, а грубая оценка К есть -')д. 14. Ключевым является индуктивное утверждение, которое должно быть справедливым в начале шага М4. Все остальные утверждения легко выводятся из этого утверждения, которое выглядит так: 0 < ь < пп 0 < / < и; 0 < и~ < 6 при 0 < ! < гп; 0 < ш < Ь при 0 < ! < и; 0 < ил < Ь при 0 < ! < /+ пц О < Ь < Ь; и в обозначениях, введенных в ответе к упр.
4, (ьвь<. — ь ..ьвв)ь+ЬЬьв = и х (вь-ь ..ве)ь+ (иь-ь .. иь)ь х взбь. 15. Ошибка неотрицательна и меньше (и — 2)Ь " '. (Аналогично, если проигнорировать произведения при ь+/ > и+3, ошибка будет ограничена величиной (и-3)6 " ~, и т. л. Но, вообще говоря, для получения правильно округленного результата необходимо вычислять все произведения.) Дальнейший анализ показывает, что корректно округленный результат перемножении дробных частей чисел в формате с плавающей тачкой почти всегда может быть получен при вычислительных затратах, почти вдвое меньших, чем при вычислении полного произведения с удвоенной точностью.
Более того, выполнив проверку, можно убедиться, что случаи, в которых необходима полная точность, крайне редки. (См. 1Ч. Кгапб!с)ь, 3. В. Лойпаап, Ргос. ГЕЕЕ Бушр. Сошрпьег АПСЬшебс 11 (1993), 228-233.) 16. 61. Присвоить г+- О, 2 ь- и — 1. 82. Присвоить ьвь ь- ((гЬ+ иу)/в), г ь- (гЬ+ и ) шод в. ББ. Уменьшить/ на 1 и, если! > О, вернуться к шагу 82. Х 1Т. и/в > и„Ь" /(в, + 1)6" ' = 6(1 — 1/(в -ь + 1)) > 6(1 — 1/(6/2)) = 6 — 2. 18. (и Ь+ и —,)/(в„, + 1) < и/(в„ь + 1)Ь" < и/в.
19. и — дв < и — дв„1Ь" ' — дв зЬ" = и„ьЬ" + + ие + гЬ" ' — Ввь-зЬ" < 6" ~(и-з + 1+ г6 — Вв„з) < О. Поскольку и — дв < О, то д < д. 20. Если д < д — 2, то и < (д — !)в < д(в„ьЬ" ' + (в з + 1)Ь" ь) — в < дв,Ь" ' + двл-26" +Ь" — в < дв„— ьЬ" +(Ьг+и -з)6" +Ь" — в = и Ь" +и„-ьЬ" +и ьЬ" + Ь" — в < и„Ь" + и -ьЬ" + и -гЬ" ~ < и.
Другими словами, выходит, что и < и, а это невозможно. 21. (Патучена Г. К. Гоялам (С. К. ОоуаЦ.) Из неравенства дв ь < 66+ и„з следует д < (и Ь + и ьЬ+ и„-з)/(и„ьЬ+ в з) < и/((в„,Ь+ в„з)6" ~). Отсюда и шабе = и — дв = в(1 — а), где 0 < а = 1+ д — и/в < д — и/в < и(1/((в -ьЬ+ в — г)6" ~) — 1/в) = и(в ьЬ" з+ )/((в„ьЬ+в„з)6" тв) < и/(в„ьЬв) < д/(в„ьЬ) < (Ь-!)/(в„ьЬ), которое ограничено величиной 2/Ь, так как в ь > —,'(Ь вЂ” 1).
22. ПУсть и = 4100, в = 588. Возьмем сначала д = (ььь! = 8. Однако видим, что В 8 > 10(41 — 40) + О. Тогда полагаем д = 7 и получаем 7 8 < 10(41 — 35) + О. Но число 588, умноженное на 7, равно 4116, так что правильное частное будет д = 6. (Межлу прочим, данный пример показывает, что для 6 = 10 теорема В при данных предположениях не может быть улучшена.) 23.
Очевидно, что о(6/(о+ 1Ц < (о + 1)(6/(о+ 1Ц < 6, поэтому при е > 6/2 выполняется левая часть неравенства. В противном случае о(6/(о+ 1Ц > о(6 — о)/(о+ 1) > (Ь вЂ” 1)/2 > (6/2) — 1. 24. Приближенная вероятность равна всего лишь )оЕь 2, а не -'. (Например, если Ь = 2~~, з! вероятность того, что о ! > 2, приблизительно равна —,. Тем не менее этого еще ! достаточно много для того, чтобы оправдать выполнение специальной проверки условия б = 1 на шагах П1 и ПБ алгоритма П.) 28. 002 ЕМТА 1 1 002 200 Ч+М-1 1 00! БТА ТЕМР 1 005 ЕМТА 1 1 Ооб 10Ч 1Р 1 Переход, если о„! = Ь вЂ” 1. 007 ЕМТХ О 1 ООО ОТЧ Ч+М-1 1 002 ЛОЧ 01ЧВТХЕЫО 1 О!О 1Ы БТА 0 1 О!1 РЕСА 1 1 О!2 !АМЕ ь+3 1 Переход, если !( ~ 1.
О!3 БТЕ О+М+М 1 — А Присвоить и е„<- О. О!! 1МР 02 1 — А О!5 ЕММХ М А Умножить о на !!. О!б ЕМТХ О А 017 2Н БТХ САЫЫТ А!Ч О!2 10А Ч+М,1 А!У О!2 ЮЛ. 0 А1Ч Иначе — вычислить (6/(о + ХЦ Переход, если о„, = О. (Как в упр. 13.) 02б !1М 2В 027 ЕММ1 М+М 022 2Н БТХ САЫВТ 029 ЕОА О+М+М,1 А)Ч А А(М+ А!) А(Л1+ !Ч) (Теперь гХ = 0.) Умножить и на б. (К в упр, 12.) А(М+ !Ч) (Остаток сохранится в ячейках от 0 до О+М-1.) Если б = 1, то закончить. г11 ш 1;,1 +- и — 1.
г +- О. гАХ ! — гЬ+ и!. На этом программа деления упражнении, гАХ = О. 037 Оуб 26. (См 10! 102 102 10! 105 !Об !07 105 109 !!О !!! 21М 2В БТХ О+В+В алгоритм в упр. 18.) 08 101 0 ВЕСА 1 1 !АХ ООМЕ 1 евт1 м-1 А ЕМТА О А 1Н 101 0,1 АА! 01Ч 0 А)Ч БТА Н 1 ААг БЕАХ Б ААг ОЕС2 1 ААг 12ММ 1В А!Ч (и!, г) !- ((гАХ/гЦ, гАХ гпос) !(). 1' +- ! + 1. Повторить для и > ! > О. завершается, причем, как будет показано в следующем 27. Это число равно 8и шоб Ие = И(и шос! е). 28. Предположим (для удобства), что е имеет десятичную точку слева, т.
е. что е = (еью ге -г .. )ь После завершения шага !91 получим -' < е < 1+ 1/Ь. Тогда е ~< Ь+ 1 ! е(Ь+ 1) е(1+ 1/Ь) 1 « = 1+— (~/Ь)(е., Ц Ь Ь+ 1 ! е(Ь+ 1 — е„~) 1 е ~(Ь+ 1 — е ~) е > >— — +11 +1 Ь „+1 Величина в последнем соотношении принимает наименьшее значение при е„~ — — 1, так как зто выпуклая функция и другое ее экстремальное значение больше. ! Ь(Ь+1) !е Формулу иа шаге 742 можно переписать в виде е ь- ~ ~ —, поэтому, как и выше, находим, что е никогда не будет > 1 + 1/Ь.
1~ Ь' После одной итерации шага М2 минимальное значение е ие меньше,чем Ь(Ь ! 1) е» вЂ” 3 !е /Ь(Ь+Ц ю — 1 !е — 3 /Ь(Ь+1)+1 !!/! 1) ( . )--'~ . ) — =( 1 2 1 7 Ь(Ь+1)+11 = 1+ -+ — — — ~1+ Ь Ьз Ьт ( 1 при ! = е ~ + 1. Минимум этой величины достигается при 1 = Ь/2+ 1, нижняя граница равна 1 — 3/2Ь. Следовательно, после одной итерации шага Х2 имеем е ~ > Ь вЂ” 2. В итоге получаем (1 — 3/25)(1+1/Ь) > 1, где Ь > 5, так что потребуется еще пе более двух итераций. В случае, когда Ь < 5, утверждение легко проверяется непосредственно. 29.
Это утверждение верно, так как (и!е„... иг)ь < е. 30. При выполнении алгоритмов А и Б такое перекрытие возможно, если алгоритмы слегка видоизменить. К примеру, в алгоритме А можно так переписать шаг А2: "Присвоить 1 +- иг + ег + /с, ю. +- ! шоб Ь, Ь +- (1/Ь!", При выполнении алгоритма М значение еу может храниться в том же месте, что и в~э„, При реализации алгоритма П удобнее всего (как в программе П в упр, 26) принять, что значения г„ю,.га хранятся там же, где и и ~ ... иа. Можно также считать д йе такими же, как и и е„, .. и„, при условии, что па шаге 06 значения переменных в,э ие изменились.
(Строка 098 программы !1 может быть без вреда замеиепа иа е31628", так как величина и э„в вычислениях, выполняемых на этом шаге, пе используется.) 31. РаССМОтрИтЕ СИтуацИЮ, ПрИВЕдЕННуЮ Иа рпе. 6, ПОЛОЖИВ и = (и!Еь... и„~.~иу)З, Ках в алгоритме П. Если ведущие ненулевые разряды чисел к и е имеют одии знак, то присваиваем г ь- и — е, д ь- 1; в противном случае присваиваем г е- и+ е, д г — -1. Если теперь ~г) > )и) или ~г) = )и) и знак первого ненулевого разряда чисел к, ю ..ие совпадает с первым ненулевым разрядом числа г, то присваиваем д ь- 0; в противном случае присваиваем к!э ... и, значения разрядов числа г. 32. См.
М. г!аг)!ег, САСМ 4 (1961), 192-193; Е. Раи'!аЫ апб А. 1!гаЬп!!св, Во!!. де !'Асад. Ро!ела!эе дез Яс!епсгл, С1аээе !П, 5 (1957), 233 — 236 (см. также с. 803-804), и упр. 4 1-15. 34. См., например, В. Е. Маебег, ТЬе Магйегвабса,Уошла! 6,2 (Брбпй, 1996), 32 — 40, 6,3 (Бппипег, 1996), 37-43. 36. Имея число ф, заданное с точностью х2 ~", ф ', ф ~,, значение 1пф можно вычислить, выполняя вычитания до тех пор, пока ф " < 2 ". Накапливаемая при этом ошибка не превысит 2' ". Затем можно использовать ряд!пф = 1п((1+ф з)/(1 — ф э)) = 2(ф "+ -'ф + -'ф '~+ ). [См. статью 1Ч!!!!агп Бсйоо!!пй, ффвр!ег Тегселсепагу Мешопа1, есйьеб Ьу С. С. Кпоь! (Ьопйопс Ьопйшапв, 1915), 337 — 344.] Но еще лучше (предложено в 1965 году Дж. У.
Ренчем (мл.) (Л. %!. 1ЧгепсЬ, Зг.)) вычислить 1пф = -'!п((1+ 5 'с~)/(! — 5 Цз)) = (2ф — 1)(5 '+ —,'5 з+ 35 ь+ ). 37. Пусть З = 2', так что 5 > с)о ! > 5/2. Вместо нормализации и и о иа шаге П1 определяем два ведущих разряда о'оо числа 2'(о„со„зо„з)ь посредством его сдвига влево на е бит. На шаге ЫЗ вместо (о„с,о з) используем (о',оо), а вместо (и!вши,с.„с, и,~. 4) используем (ис, и!, й ). Значения разрядов и~и~~и~~ вычисляются путем сдвига влево на е бит числа (и!.„... и!с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
