Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 78
Текст из файла (страница 78)
Следовательно, преобразование оставляет /„ неизменным до тех пор, пока е„ вЂ” с, > 2. Поскольку и не нормализовано, оно отлично от нуля н д„ + /,4 > Ь ' — Ь т > 6 т. Ведущий, отличный ат нуля разряд /„ + /„ должеп находиться не более чем на два разряда правее разделяющей точки, и операция округления преобразует 6е+з(/, + /,) в целое, где / < 1. Доказательство будет завершено, если показкгь, что 6"+1+'(/„+/„) 6еез+'(/, +Ь е ~г'„). Из предыдущего абзаца имеем Ьеег(/, + /,) Ье+т/ + Р, = Ь"+т(/.
+ Ь е ~гг), из чего следует искомый результат для всех у < 1, Аналогичное замечание справедливо и в отношении шага М2 алгоритма М, Обратите внимание, что, когда Ь > 2 четное, такое целое число Рл существует всегда; но если 6 = 2, потребуется р+ 3 бит (полагаем 2Р„целым). Бели Ь нечетно, то целое Р„ существует всегда, кроме случая деления в алгоритме М, когда возможен остаток -Ь.
1 6. (Рассмотрите слюлай, когда е, = е„, /„ы -/„, в программе А.) Регистр А сохранит предыдущее значение знака, как и при выполнении команды 400. 7, Будем гаворитгн что число нормализовано тогда н только тогда, когда оно равно кулю или его дробная часть находится в диапазоне -' < ф < -'. Аккумулятор на (р+ 1) разрядов вполне подойдет для операций сложения и вычитания; округление (кроме случая деления) зквивалентно отбрасыванию лишних разрядов, Кажется, получилась очень привлекательная система! Можно использовать представление чисел порядком с избытком нуль, вставленным между первым и последующими разрядами дробной части и дополненным, если дробная часть отрицательна.
Так что сохраняется порядок, принятый для чисел с фиксированной точкой. В. (а) (06, +.12345679) ~Э (06, †.12345678), (01, +.10345678) Ю (00, †.94000000); (Ь) (99, +.87654321) Ю оно же, (99, +.99999999) Е (91, +.50000000). 9. а = с = (-50,+.10000000), 6 = (-41,+.20000000), И = (-41,+.80000000), у ж (11, +.10000000). 10. (аО, +.99999000) ОЛ (55, +.99999000). 11. (50, +.10000001) З (50, +.99999990).
12. Если 0 < Щ < //„/, то (/„! < (/, / — Ь е; следовательно, 1/Ь < 1/„/Я < 1 — Ь е/Ц„) < 1-6- . Е О <)/) <Щ .. 1/Ь < (/.'// ~/6 < ((1-6- )/(1/6))/6=1-6-е. 13. См, Ю. М1сйае! Ъойе, 1ЕЕЕ Тгаазасполз С-22 (1973), 577-586, а также упр. 4.2.2-24, 14. Р1Х 571 9Р Подпрограмма ПТ-в-ФТ. ВТЬ ТЕВР 691 ТЕВР(ЕХР) гП е- е.
61.А 1 гА+- х////О. Нуль на входе? ЛАХ 9Р ОЕС1 1 СИРА О-(1:1) ЛЕ е-4 ЕИИ1 "Я-4Ф1 ХАМ РХХОТРЕО ЕМТХ О ЕВАХ 0,1 СИРХ 1//2ь ЛА 9Р 10 ь+2 УАО 9Р Если ведущий байт равен нулю, снова сместить влево. Абсолютное значение слишком ыьтико7 В некоторых случаях становится нечетным, поскольку Ьг'2 четно. При необходимости округлить. АгЫ ш1 (переполнение невозможно), Выход из подпрограммы. $ БТА е+1(О:О) 1ИСА 1 9М Л(Р гА+-в . г12+-е . Удалить целую часть н. Дробная часть отрицательна: найти ее дополнение.
Размер оюна минус единица $ 16. Если (с! > Щ то установить 1 <-НЗс, в(-сб(гЗИ); х+-(аЗ(ЬЗг)) Зв, у+-(Ь З (а З г)) За В противном случае установить г+-сЗМ, в+-г(З (гЗс); х+-((аЗ г) ЗЬ) Зв, у+- ((ЬЗг)За)Зв. Тогда г + (у есть искомая аппроксимация (а + Ь()/(с + сй). (САСМ 5 (1963), 435, Другое алгоритмы для выполнения арифметических операций с комплексными числами и вычисления соответствующих функций описаны в работе Р.
дупл, ВТТ 2 (1962), 232-255; см. также Рап( Раен!апо, САСМ 10 (1967), 665.) 15. РР БТХ ХОЧ БТА ЕИТХ 651 502 РЕС2 52ИР Я.А ЕИТ2 ЛАМИ ЕИИ2 БЕАХ ЕМТ2 ЛХИХ ЛАХ 1ИСА АОО 1Н ХИС2 ЛИР БИ ЕОО ЮИ1 СОМ ЕХТТР ОРАО ТБИР О ТЕИР(ЕХР) 0 ь+3 0,2 О 1Р 0,2 0,2 0 е+3 е+2 1 ИМ1 Ц МОХИ 1(1:1) 88-1,88-1(1:4) Подпрограмма для выделения дробной части.
Снятие блокировки переполнения. ТЕИР Ф- и. Добавить размер слова минус единица. Подготовка к нормализации результата. Нормализовать,округлить и выйти из падпрограммьь 17. (См. ЕоЬе«Ч 14огпэ, 1ЕЕЕ Тглпэагболэ С-20 (1971), 1578 — 1579.) Для такой системы анализ ошибки более сложен, поскольку здесь предпочтительнее испольэовать арифметику интервалов. 18. Для положительных чисел решение таково. Сдвигать дробную часть влево до тех пор, пока не окажется, что 1« = 1; затем округлить, затем, если дробная часть равна нулю (нереполнение при округлении), снова сдвинуть вправо. Для отрицательных чисел решение таково. Сдвигать дробную часть влево до тех пор, пока не окажется, что 1« = 0; затем округлить, затем, если дробная часть равна нулю (исчезновение значимости при округлении), снова сдвинуть вправо.
19. (43+ [е,. < е ] — [переполнение дробной части! — 10 [результат — нуль]+ 4 [абсолютная величина округлена до]+ [первый округленный разряд равен «]+ 5 [округленные разряды ь 2 равны 10...0]+ 7[переполнение при округлении]+ 7АТ+ (11[Я>0] — 1) [гХ принимает ненулевые разряды]) и, гдг А«есть число сдвигов влево при нормализации. Максимальное время 73и получается, если, например, и =+50 01 00 00 00, еж -46 49 99 99 99, 6 = 100. [Учитывая данные из раздела 4.2.4, время будет иметь порядок 45.5и.] РАЗДЕЛ 4.2.2 1. и О е = и О« -е = — е Е и = — (е «9 -и) = -(е О и), 2. и«рх > и«90 = и, как следует из (8), (2), (6), поэтому сновав силу(8) (ийх)ше > ише. Аналогично из (8) и (6) вместе с (2) следует, что (ай«х) ш(об«р) > (на«х) «9 е. 8. и = 8.0000001, е = 1.2500008, ш = 8.0000008; (и З е) 4« ш = 80.000064, и 46 (е б«ш) = 80.000057.
4, Да; пусть 1/и ш е = ш, где е велико. 5. Не всегда, например для чисел и = е = 9 в десятичной системе, 6. (а) Да. (Ь) Толькодля Ь+р < 4 (попробуйте проверить си = 1 — Ь р). Ноем, упр. 27. 7. Если и и е — последовательные числа с плавающей точкой, и й е = 2и или 2е. Когда это 2е, мы часто пеленаем иФ ше«3« < 2еО«, Например, и ж (.10...
001)ь, е ж (.10 010)э, и О«е = 2е и иоь + сот = (.10... 011)ь. 8. (а) -, ш', (Ь), ж; (с), щ, (д); (е) 9. [ — [ < [и- [+[ — [ < ~ ьп(6'" «,6'" )+ гп(6',Ь " ) < 6'" +. 6' < (с«+ еь) «пах(6'" ь, Ь'" "). В общем случае усилить этот результат нельзя, Например, можно было бы взять е очень малым по сравнению с обоими порядками е„и е, но это означало бы, что и — м слишюзм велико яри сделанных предположениях. 10. Если ар > 1 и а«> 1, полУчим ( а«... ар «а )ь З ( 9... 99)ь = ( а« ...аР «(аР— 1))«4 здесь "9" есть 6 — 1.
Далее, (.а«...ар «ар)ь ~В(10 ..0)ь = (.а«., ар «0)ь, так что, если Ь > 2 и ар > 1+ [а«> Щ, умножение оказывается не монотонной операцией, Но в случае, когда Ь = 2, используя то же самое рассуждение, можно доказать, что умножение является монотоннъпа. Очевидно, "некий компьютер" имеет Ь > 2. 11.
Можно положить без ущерба для общностн рассуждений, что х есть целое, 0 < х < 6". Если е < О, то1 = О. Если 0 < е < р, то х — 1 имеет не более р+1 разрядов, причем наименее значимый равен нулю. Если е > р, то х — 1 = О. [Результат справедлив и при более слабой исходной посылке [1[ < Ь', в этом случае можно было бы получить х — 1 = 6', если е > р.] 12. Предположим, что е„= р, е, < О, и > О, Случай 1: и > Ьр . Случай (1, а): ш = и+1, е > Ь.,е„=О. Тогдай = вилик+1,е' =1, и" = и, е' =1илиО. Случай(1,Ь): ы = и, )е] < -.
Тогда а' = и, е' = О, й' = и, е" = О. Если ]е) = -' и допустимо более общее правило округления, можно было бы получить и' = и щ 1, й' ~1, Случай (1. с): ти = и — 1, е < --, е, = О. Тогда и' = и или и — 1, е' = -1, й' ы и, е" = -1 или О. Случай 2: и = Ь» . Случай (2, а): а~ = и+ 1, в > -', е, = О, как в (1, а). Случай (2, Ь): ге=и,)е( < -', й > и,каке(1,Ь). Случай(2,с): в =и, (е] < -', и' < а. Тогда а' = а — 1/Ь, где е = у/Ь + е~ и ]в~] < 1Ь ' для некоторого положительного целого у < $5; имеем е' = О, и" = и, в" = у/Ь, Случай (2, 6): ы < и. Тогда ~е = и — у/Ь, где е = -б/Ь + е~ и (е~) < -'Ь ' для некоторого положительного целого б < Ь; имеем (ь',и") = ( — 1/Ь,и) и (и', е' ) = (и, -у/Ь) или (и - 1/Ь, (1 —,1)/Ь); последний вариант возможен, только если «~ =15 ~.
В любом случае ахи = а — и, «З«' =е — е, ахи ма — й, «З«е же — е", гоипб(ы-а — е) = 㫠— а-е. 13. Поскольку пщпг)(х) = 0 тогда и только тогда, когда х = О, нужно найти множество пар целых чисел (щ, и), обладающих таким свойством: результат щ З и есть целое число тогда и только тогда, когда целым числом является щ/и. Предположим;что (т(,]а) < Ь'. Если гл/и есть целое, то т З и = гп/и — также целое. И наоборот, если т/и яе есть целое, а т З и — целое, имеем 1/(и) < )т З п — щ/и] < Цт/п(Ь' ».
Следовательно, (щ) > 2Ь» Зиачит, ответ таков: нужно потребовать, чтобы выполпялись условия ]т] < 25» ' и О < (и] < Ь». (Возможно и чуть менее жесткое ограничение.) 14. ((иЗ«)Зы-аеы) < )(иЗ«)Згв — (иЗ«)щ(+)м)(иЗ«-ае] < бщв„1х,„+Ь' е б»вг < (1 + Ь)бщхщх . Теперь ]еще,1х — е„яыяи1) < 2; таким образом, в качестве искомого результата можио взять с = Ьз(1 + Ь)Ь 16. Из и < е следует, что (и Ю и) З 2 < (и З е) З 2 < (е З е) З 2. Таким обрезом, сформулированное в задаче условие остается справедливым для любых и и е тогда и только тогхэг, когда оио справедливо для любых и = е.
Для основания Ь = 2 исходиое условие справедливо всегда (эа исключение случая, когда возникает переполиеиие); ио при Ь > 2 существуют числа е ЭЕ гх, такие, что е З е = и З ы. Значит, сформулированное в задаче условие ие выполняется. [С другой стороны, формула и З ((е З и) З 2) действительно дает среднюю точку, лежащую внутри иитервела. Докаэетельсгпэо. Достаточио показать, что и+(«Зи) З2 < в, т е. («Зи)З2 < в — и; легко проверить.
что гоипг((этоох(х)) < х для любых х > 0.] 16. (а) Изменение порядка появится в суммах 2 ю = 11.111111, 2 „, = 101.11111, 2 1001.1102, '] ее, = 10001.020, 2"эипе = 100000,91, 2 име,э ы 1000000.0: таким образом, = 1109099.1. (Ь) После определения суммы 2 „", 1.2345679 = 1224782.1 вычисления в соответствии с (14) приведут к попытке определить квадратный корень из —.0053187053.
Но в этом случае вычисления в соответствии с (15) и (16) будут точными. ]Если хь ж 1 + ((Ь вЂ” 1)/2]10 ", то вычисления в соответствии с (15) и (16) дадут ошибку порядка и. Более детальный анализ точности вычисления стацдартиого отклонения приведен в работе СЬэп апд Ьеиы, САСМ 22 (1979), 526-531.] (с) Нужно показать, что и З ((е З и) З Ь) находится между и и е; см. упр. 15. 17. ГОЕР ЗТЛ 9Г Подпрограмма для сравиения чисел в формате с плавающей точкой. 10Г ОГЬО Убедиться, что индикатор переполнения выключен, ЕТХ ТЕАТР 7.046 ТЕИР в+- -е. (Сюда скопируйте строки 07-20 из программы 4.2.1А.) ЬЭХ ГГ(0: О) Присвоить гХ значение "нуль" со знаком, совпадающим со знаком /„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
