AOP_Tom2 (1021737), страница 188
Текст из файла (страница 188)
Наконец, при выполнении команды в строке 32 переполнение невозможно, так как произведение /»/» должно быть меньше единицы. 4. Вставьте команду»ХОЧ ОРЕО; ЕИТ1 0" между строкамиОЗ и04. Замените строки 21 — 22 на »100 ТЕИР(АОБ); ХИОЧ »+2; 1ИС1 1", а строки 28-31 на »БЬАХ Б," АОО ТЕИР; ЗИОЧ »+2; ХИС1 1; ЕИТХ 0„1; БИС 5". Таким образом,ко времени выполнения будет добавлено пять строк кодаи только 1, 2 или 3 машинных цикла. б.
Вставьте 410Ч ОН.О» после строки Об. Замените строки 22, 31, 39 на »БИАХ 0,1", »БЬАХ б", »АОО АСС" соответственно. Между строками 40 и 41 вставьте команды »ОЕС2 1; 1ИОЧ ОИОИИ; 1ИС2 1; 1ИСХ 1; БЕС 1". (Таки подмывает удалить»ОЕС2 1» и заменить ее командой»БТЕ ЕХРО", но тогда команда»1ИС2 1» может вызвать переполнение регистра 212)) Таким образом, программа увеличится на шесть строк; время выполнения уменьшиглсл на 3», если только не возникнет переполнения при работе с дробной частью. В этом последнем случае время выполнения увеличится иа 7и.
Преобразование в формат с удвоенной точностью. Очистка гХ. 6. ОООБЬЕ БТЛ Е11ТОГ ЕИТ1 О ЯТА ТЕИР 1Л)2 ТЕИР(ЕТР) 1ИС2 ЦЦ-Ц ЯТЕ ЕТРО ЯЬАХ 1 ЛМР ОБОИМ Н2 < — е. Поправка на разность избытков. ЕХРО е- О. Удалить порядок. Нормализовать и выйти из подпрограммы. Преобразование в формат с однократной точностью. Убедиться, что индикатор переполнения выключен. Я1ИОЬЕ ЯТЛ ЛОГ ЯТА ЬО2 ОЕС2 ЯЬАХ ЛИР Е11ТГ ОГЬО ТЕМР ТЕИР(ЕХРО) ЦЦ-Ц 2 БОНИ г12 ь- е.
Поправка на разность избытков. Удалить порядок. Нормализовать, округлить и выйти из подпрограммы. $ 7. Все три программы дают нуль в качестве результата тогда и только тогда, когда точный результат должен равняться нулю, так что не стоит беспокоиться о нулевых знаменателях в выражениях для относительной ошибки. Наихудший случай для программы сложения действительно плох. Перейдем для наглядности к десятичным обозначениям, Если входные значения слагаемых — 1.0000000 и .99999999, то ответ будет равен Ь ~ вместо Ь э. Таким образом, максимальная относительная ошибка б~ равна Ь вЂ” 1, где Ь— размер байта.
Что касается умножения и деления, то можно предполагать, что оба операнда положительны и порядки обоих операндов равны ЦЦ. Максимальную ошибку умножения легко можно найти, проанализировав рнс 2. Если иь > 1/6, то 0 < ие — в б) о < 36 э + (6 — 1)6 е, так что относительная ошибка ограничена значением (6+ 2)6 э. Если 1/Ь < ве ( 1/Ь, то 0 < ио — и 8 о < ЗЬ э, так что в этом случае относительная ошибка ограничена величиной ЗЬ э/ие ( ЗЬ ~, Возьмем в качестве бз ббльшую из этих двух оценок, а именно — ЗЬ В случае деления требуется более тщательный анализ программы П. Величина, действительно вычисленная подпрограммой, будет равна и — Л вЂ” Ье((а — Ьл) (Б — б') -бь) -б„, где а = (им + еи~)/Ье,ч, Д = ш/Ьоы; неотрицательные ошибки отбрасывания, равные (б, б', о", Зе'), не превышают (Ь 'е, Ь ~, 6 ~, 6 е) соответственно; наконец, б„(ошибка, возникающая при отбрасывании в процессе нормализации) неотрицательна и меньше либо 6 э,либо Ь э в зависимости от того, происходит ли сдвиг.
Действительное значение частного есть о/(1 + Ье/)) = и — беар + А~од~о"", где 3"" — неотрицательная ошибка, возникающая при отбрасывании бесконечного ряда в (2). Здесь б"" < е~ = Ь 'е, так как ряд знакопеременный. Следовательно, относительная ошибка равна абсолютному значению выражения (ЬеЮ' + ЬеблД/а + Ьебш/а) — (д/а + Ьед'о"/а + Ь~ДЧлл + Ю„/а), умноженному на (1+бе/)). Положительные члены этого выражения ограничены величиной Ь э+Ь е+Ь е, а отрицательные ограничены (по модулю) величиной 6 е + 6 '~ + 6 э плюс вклад от фазы нормализации, величина которого может достигать 6 ~. Таким образом, ясно, что потенциально наибольшая составляющая относительной ошибки возникает в процессе выполнения нормализации, и можно считать, что значение бз = (Ь + 2)Ь е является надежной верхней границей для относительной ошибки.
8. Сложение. Если е„< е„+ 1, то вся относительная ошибка возникает в процессе нормализации и она ограничена значением Ь г. Если е„> е,. +2 и если знаки операндов совпадают, то, опять же, вся ошибка может быть отнесена на счет нормализации; если знаки противопатожны, то ошибка, связанная со сдвигом разрядов из регистра, противоположна ошибке, возникающей после этого в ходе нормализации.
Обе составляющие ограничены значением Ь ~; следовательно, 6~ = Ь ". (Это суп»ественно лучше результата упр. 7.) Умножение. Анализ, аналогичный выполненному в упр 7, дает бз = (Ь+ 2)Ь э. РАЗДЕЛ 4.2.4 1. Так как переполнение дробной части может происходить только при операндах одного знака, искомая вероятность равна вероятности переполнения дробной части, деленной на вероятность совпадения знаков операндов, т.
е 7%/(-'(91%)) 15%. 3. 1об ~ о 2 4 — 1об~ о 2 3 = 1.84834% 4. Страницы были бы потрепаны равномерно. 5. Вероятность того, что 10/и < г. равна (г — 1)/10+(г — 1)/100-Ь = (г — 1)/9. Поэтому в рассматриваемом случае ведущие цифры распределены равномерно, например ведущая цифра 1 встречается с вероятностью -'. 9 6. Вероятность того, что имеется три нулевых ведущих бита, равна 1об,е2 !. вероятность того, что два ведущих бита нулевые, равна 1об,е 4 — 1об,е 2 = -': аналогично и для лвух других случаев. "Среднее" число нулевых ведущих битов равно 1-', так что "среднее" число "значащих битов" есть р + -'.
Однако наихудший случай, р — 1 значащих битов, встречается с довольно высокой вероятностью. На практике, как правило, оценки ошибок необходимо проводить на основе наихудшего случая, поскольку цепь вычислений настолько "прочна", наскачько прочно слабейшее звено. Как следует из анализа ошибок в разделе 4.2.2, верхняя граница относительной ошибки округления равна 2' г для шестнадцатеричной системы счислении.
При работе в двоичной системе счисления »южно получить р + 1 значащих битов во всех нормализованных числах с относительной ошибкой округления, ограниченной значением 2 ' " (см. упр. 4.2.1-3). Обширные вычислительные эксперименты подтверждают утверждение, что вычисления в двоичном формате с плавающей точкой дают более точные результаты, чем аналогичные вычисления в шестнадцатеричном формате с плавающей точкой, даже когда точность представления двоичных чисел равна р бит, а не р+ 1.
Из табл. 1 и 2 видно, что шестнадцатеричная арифметика может быть сделана чуть более быстрой, так как для нее необходимо меньше циклов при масштабировании посредством сдвига вправо или нормализации посредством сдвига влево. Но этот фактор оказывается несущественным в сравнении с теми неоспоримыми преимуществами, которые имеет выбор Ь = 2 над другими основаниями (см. также теорему 4.2.2С и упр. 4.2.2. 13, 15, 21), в особенности, если принять во внимание, что можно достичь той же скорости вычислений в двоичном формате с плавающей точкой, что и в шестнадцатеричном, ценой очень незначительного повышения суммарной стоимости процессора. 7.
Предположим, что (Г(10"~ 5") — Г(10 )) = 1о85" /)ой 10 и что (г(10~ 4») — г'(10» )) = 1о84" /1о810»; тогда (г (10 5 ) — Г(10 4 )) = 1обьа 4 для всех Ь. По данному малому положительному числу е выберем д > 0 так, чтобы Г(х) < е при 0 < х < б, и выберем М > 0 так, чтобы Р(х) > 1 — е при х > М. Можно взять /с столь большим, что будут выполняться неравенства 10 ~ 5~ < 5 и 4ь > Л»; следовательно, в связи с монотонногтью функции Г получаем (Р(10 5 ) — Р(10 4 )) < ) (Р(10 и 5 ) — Р(10 ~ ! 5 ))+ 2 (Р(10 Р" ь ! 4 ) — Г(10ь~.4 )) Ьо бо = Р(10 5")+1 — Г(10 4") < 2е. 8.
Если о > г, то Ро(10" о) равно 1 при малых и и равно О, если (10" о) > (1О" г). Наименьшее п, для которого так бывает, может быть произвольно большим, так что для А»о(г) нельзя дать никакой равномерной оценки, не зависящей от о. (Вообще говоря, в учебниках по анализу доказывается, что из такой равномерной оценки следовало бы, что предельная функция Яо(о) непрерывна, а это не так.) 9. Пусть ды до,...
таковы, что Ро(п) = д»(",, ') +до(", ') + - для всех п. Тогда Р~(п) = 1 д»( о )+2 до( 3 )+ длявсехщнп. 10. Если 1 < г < 10, производящая функпня С(х) имеет простые полюсы в то*»ках 1 + и ш где и» = 2япд/ 1в 10. Следовательно, ) !об»' ! ~ 1 +ш е ! Е( ) 1 — х по (1и 10)(х — 1 — ш„) »»о где Е(х) есть аналитическая функция на всей плоскости. Таким образом, если д = агсгап(2 г/ 1и 10), то 2»е "ы' — !» !и 10 ~ 'т ш (1 + ш„)"' / в!п(тпрр+ 2я!ойш г) — о!п(тпд) ( 1 = !ойш г — 1+ 0( к(1+4яо/(1п10)о)»»(1+16яо/(!п10)г) ~ / 11. Если величина (!ой„!/) шоб 1 равномерно распределена в интервале (О .. 1), то так же распределена н величина (!обо 1/(»') шоб 1 = (1 — !обо У) шод 1.
12. Имеем г» г' Л(х) = /(х) ох 9(х/Ьх)/Ьх -!- / /(Х) г!х д(х/х)/х; мь следовательно, Л(х) — !(х) /'* д(х/Ьх) — 1(х/Ьх) /' д(х/х) — 1(х/х) 1(х) /,~о 1(х/Ьх) ,/, !(х/х) Так как /(х) > О, )(Л(х) — !(х))/!(х)) < /; /(х)о!хА(д) + / /(х)»(хА(д) для всех х, то .4(Л) < А(д). В силу симметрии А(Л) < А(/). [Ве1! Яузсеш ТесЛ. о'. 49 (1970), 1609-1625.) 13. Пусть Х = (!обо»/) шод 1 и У = (!обо 1») шод 1, так что Х и У независимо и равномерно распределены в интервале (О .. 1).
Ни одного сдвига влево не потребуется тогда и только тогда, когда Х + У > 1, и это происходит с вероятностью (Аналогично результат выполнения деления по алгоритму 4.2.1М не нуждается в нормализующих сдвигах с вероятностью —; здесь достаточно более слабого предположения » о соева»!емки распределений независимых операндов.) 14.
Для удобства вычисления проводятся здесь для 6 = 10. Если Й = О, то вероятность переноса равна 01 10 ( — //' ~ Ф !п10/ /~й»,г<~е г у » ггй!е (рис. А — 7). Интеграл равен 1 10 0 00 Рис. А — 7. (Последний интеграл, по существу, является»билогарифмическим",) Значит, вероятность переноса при Й = 0 равна (1/!в10) (л /б — 22"„>,1/и~10") = .27154. (Замечание. Если 6 = 2 н Й = О, переполнение дробной части происходит всегда, так что этот вывод подтверждает справедливость соотношения 2,„>, 1/иг2" = я~/12 — (!и 2) г/2.) Если Й > О, вероятность равна 2. а а — ~~ а < -<Ли 1 -с <г< ь! )~ !<г< г ~!<<я<» — е» ь — г так как и — ги > Ж Аналогичное противоречие возникает и если йп!вша < О.
Таким образом, если 6 = 10, переполнение дробной части должно возникать с вероятностью приблизительно.272ре+,017р~+.002рг+ . Когда 6 = 2, соответствующие величины равны ре+.055р~ +,2ВВрг+ 137рг+.Об7р4+ ОЗЗрг+ 01бре+ ООВрг+.004рг+.002рг+.001рьо+ Если теперь воспользоваться значениями вероятностей из табл, 1, разделив их на .91 для устранения нулевых операндов, и принять, что вероятности не зависят от знака операндов, можно при 6 = 10 предсказать значение вероятности окало 14% против 15% из упр. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
