Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 79
Текст из файла (страница 79)
Принудительно установить знак "минус". Если переполнения нет, сделать еще один перенос в старшую половину. (Теперь гА < 0.) гА+- ~ю ~ — ~гАЬ (Теперь гА > О.) гА е- ш с правильным знаком. Нормализовать и выйти из подпрограммы. Ненормализованный или нулевой делитель. 08 дЛ 06 06 08 00 10 12 18 14 15 ЯТА Я.АХ ЯТА ЯТХ ЕВА ЯОВ ЗТА ЕИТ2 1.0А 1.0Х ЯЛ,АХ ЯНАХ 01Ч ТЕИР 2 АНС АНСХ АСС(ЕХРВ) ТЕИР(ЕХРВ) ЕХРО СО+1 АСС АССХ 2 1 АНС АСС б АНС АССХ АНСХ(1пй) О АНС(АВЯ) ВЧХНОВ АСС(АВЯ) 3 АССХ(АВЗ) 1 ИИ1 е+2 1 5 АСС(АВЗ) АСС(АВЗ) АСС ВИСНИ ЗО Удалить порядок. (См, алгоритм 4.2.1М.) Если произошло переполнение, оно будет обнаружено ниже, юы. Использовать остаток для дальнейшего деления. 33 1Н щ0 1(1:1) 89 1И1 СОМ 18-1, ВТТВ-1 (1: 1) Размер слова минус единица.
! Ниже приведена таблица с приближенными значениями средних времен выполнения для рассмотренных программ вычислений с удвоенной точностью в сравнении с соответствующими характеристиками подпрограмм вычислений с однократной точностью из раздела 4.2.1. Уджшниая точность 84и 88и 109и 126.5и Однократная точность 45.5и 49.5и 48и 52и Сложение Вычитание Умножение Деление Дополнительная информация относительно обобщений методов нз этого раздела для вычислений с утроенной точностью в формате с плавающей точкой приводится в работе У. ПгеЬе, САСМ 8 (1965), 1У5-1УТ ]((и Э е) — (и/о)) /(и/о) ] . УПРАЖНЕНИЯ 1.
]!б] Попытайтесь вручную реализовать методику делении с удвоенной точностью числа 130 000 на 314 139, полшая, что е = „1 . (Положите (и„,и~) = (.130, 000) и (о,ш) (.314,.139) и найдите частное с помощью метода, описанного в тексте ноеве формулы (2).) 2. ]30] Стоит ли вставлать между строками 30 и 31 программы М команду "ВВТХ 0" с тем, чтобы предотвратить нежелательное влияние на точность результатов информации, оставшейся в регистре Ху 3. [М30] Объясните, почему при выполнения программы М не может произойти переполнения. 4. ]33] Как следовало бы изменить программу М, чтобы достичь повышения точности за счет сдвига вертикальной линии, гкиазанной на рис. 4, на одну позицию вправоу Перечислитее все необходимые изменения и определите, квк изменится при этом время выполнения. б. ]34] Как следовало бы изменить программу А, чтобы повысить точность за счет перехода к аккумулятору размером 9 байт вместо 3 байт справа от разделяющей точки? Перечислите все необходимые изменения и определите, как изменится при этом время выполнения.
О. ]38] Предположим, что в одной и той же основной программе используются и подпрограммы с удвоенной точностью из этого раздела, и подпрограммы с однократной точностью из раздела 4.2.1. Разработайте подпрограмму, которая переводит чигло из формата с однократной точностью в формат с удвоенной точностью соответственно (1). Разработайте также другую подпрограмму„которая переводит число в формате с удвоенной точностью в число в формате с однократной точностью (илн сообщает о переполнении или исчезновении порядка, если преобразование невозможно).
7, ]М30] Оцените точность вычислений в подпрограммах этого раздела, работающих с форматом удвоенной точности, подыскав подходящие постоянные бп бэ и бэ, которые могут служить верхними границами для относительных ошибок ]((и ш о) (и+ о))/(в+ о)], ]Ни 9 э) - (и х е))/(и х е)], 9. [МА8[ Оцените (и смысле упр. 7) точность усовершенствованных подпрограмм вычислений с удвоеююй точностью нз упр. 4 и 5. 9.
[М43] В работе Т. Л. 11еккет, Хишег, Маей, 19 (197Ц, 224-242, предлагается альтернативный полхол к вычислениям с удвоенной точностью, полностью базируюшийся на методах вычислений с однократной точностью. Например, теорема 4.2.2С утверждает, что и+ и = ш+ г, где ш = идти и 1 = (и Э ш) Ю и, если [и[ > [е[, а основание системы счисления равно 2. Здесь [г[ < [ш[/2г, так что пару (ш, г) можно рассматривать а качестве версяи и+ и е удвоенной точностью. Для сложения двух таких пар (и, и') ш (е, и'), гле [и'[ < [и[/2г и [и'[ < [е[/2г, [и[ > [и[, Деккер предложил точно вычислить сначала и+ е = в + г, затем — приближенное значение остатка е = (гЮ и') ~Э и' н наконец вернуть в вызывающую программу и качестве результата значение (в 41 е, (ш Э (ш 9 е)) ш е). Проанализируйте точность н эффективность такого подхела в случае, когда он иепольэуегся рекурсиено Лля вычислений е учетверенной точностью. 4.2.4.
Распределение чисел в формате с плавающей точкой Чтобы дать усредненную картину поведения алгоритмов, использующих арифметические операции с числами в формате с плавающей точкой (и, в частности, чтобы определить среднее время выполнения таких алгоритмов), потребуется некоторая статистическая информация, позволяющая подсчитать частоту появления различных случаев. В этом разделе будут проанализированы эмпирические и теоретические свойства распределения чисел в формате с плавающей точкой.
А. Программы сложения и вычитания. Время выполнения операций сложения и вычитания чисел с плавающей точкой в значительной мере зависит от исходной разности порядков, а также от числа необходимых шагов нормализации (влево или вправо). До снх пор неизвестна хорошая теоретическая модель, которая предсказывала бы ожидаемые характеристики, но мы располагаем результатами обширных эмпирических исследований, проведенных Д.
У, Суини [П. %. Бшеепеу, ЖМ БуэГешэ Х 4 (1965), 31-42[. При помощи специальной программы трассировки Сукин проследил выполнение шести "типовых" программ вычислений большой гложности, отобранных в различных вычислительных лабораториях, и тщательно исследовал каждую операцию сложения и вычитания чисел с плавающей точкой. В процесс сбора этих данных было вовлечено более 250 000 таких операций. Примерно одной из каждых десяти команд, выполненных тестируемыми программами, была либо гА00, либо г969.
Поскольку вычитание есть не что нное, как сложение, в котором второй операнд взят с противоположным знаком, все такого рода статистические данные можно рассматривать как относящиеся только к сложению. Результаты, полученные Суини, можно подытожить гледующим обрезом. Одно из двух слагаемых равнялось нулю примерно в 9% всех случаев, и обычно это был аккумулятор (Асс).
Остальные 91% случаев распределились примерно поровну между одинаковыми и противоположными знаками операндов, а также примерно поровну между случаями, когда [и[ < [о[ и когда [е[ < [и[. Вычисленный результат равнялся нулю примерно в 1.4% случаев. Поведение разности между порядками приблизительно описывалось распределениями вероятностей, приведенными в табл.
1, для разных значений основания Ь. Таблица 1 ЭМПИРИЧЕСКИЕ ДАННЫЕ О СООТНОШЕНИЯХ МЕЖДУ ОПЕРАНДАМИ ПЕРЕД ВЫПОЛНЕНИЕМ СЛОЖЕНИЯ Таблица 2 ЭМПИРИЧЕСКИЕ ДАННЫЕ О НОРМАЛИЗАЦИИ ПОСЛЕ ВЫПОЛНЕНИЯ СЛОЖЕНИЯ (Строка '"Свыше 5" в таблице содержит, по сути, вге случаи, когда один операнд был равен нулю, но в строку "В среднем" они не включены.) Когда и и е имеют одинаковые знаки и нормализованы, при вычислении суммы и + е либо требуется осуществить сдвиг на один разряд ещаео (в связи с переполнением дробной части), либо вообще не требуется выполнять сдвиги в процессе нормализации.
Когда а и е имеют прогивоиоложные знаки, при норивлизации происходит сдвиг влево на нуль или более разрядов. В табл. 2 представлены данные наблюдений за распределением количества сдвигов, В последнюю строку вошли все случаи, когда результат был равен нулю. Среднее число сдвигов влево в процессе нормализации равнялось примерно 0.9 для 6 = 2, около 0.2 — для б = 10 нли 16 и около 0.1 — для 6 = 64. В. Дробные части. Дальнейший анализ программ, работающих с числами в формате с плавающей точкой, можно проводить на основе сташистичесхоео распределения дробных частей случайно выбранных нормализованных чисел.
Здесь обнаруживаются весьма удивительные факты и имеется интересная теория, объясняющая зги феномены. Для удобства временно предположим, что мы имеем дело с числами в десятичной системе счисления; последуюпгие рассуждения легко распространяются на любое другое положительное основание б. Предположим, что дано '"случайное" положительное нормализованное число (с, у) = 10' у.
Поскольку 1 нормализовано, его ведущий (наиболее значимый) разряд равен 1, 2, 3, 4, 5, 6, 7, 8 или 9, и, казалось бы, естественно предположить, что кяокдая из этих цифр встречается в качестве ведущей приблизительно в 1/9 всех случаев. Однако на практике картина оказалась соверщенно иной. Например, ведущий разряд равен 1 более чем в 30% случаев! Один из способов проверить это утверждение состоит в том, чтобы обратиться к таблице физических постоянных (наподобие скорости света, гравитационной постоянной и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
