Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 68
Текст из файла (страница 68)
(Так как предполагается, что и нормализовано, на этом выполнение алгоритма можно было бы и закончить., но часто полезно использовать операцию сложения с нулем для гарантированной нормализации любого, возможно, и ненормализованного, числа.) Аб. [Масштабировать, сдвинув вправо.] Сдвинуть У, вправо на е„— е,, позиций, т. е.
разделить У„на Ь'" '"; [Замечание. Величина сдвига может достигать р+ 1 разрядов, вследствие чего для выполнения следующего шага (сложения дробной части У„с У,) потребуется аккумулятор, способный хранить 2р+1 цифр по основанию 6 справа ат позиционной точки, Если такого вместительного аккумулятора нет, можно сократить сдвиг до р + 2 или р+ 3 разрядов, но с соответствующими предосторожностями; подробности обсуждаются в упр. Ь.] Аб. [Сложить.] Установить Уэ <- Уь + У" А7. [Нормализовать,] (В этот момент (еи, У ) представляет сумму и и е, но [У [ может содержать более р цифр и может быть больше единицы нли меньше 1/6.) Выполнить описываемый ниже алгоритм Х, который нормализует н округлят (е„„У ), а также сформирует окончательный результат.
Алгоритм Х (Нормализация). ьррубый порядок" е и "сырая дробная часть" У приводятся к нормализованному виду с округлением при необходимости до р разрядов. В этом алгоритме (рис. 3) предполагается, что [У[ < Ь. И1. [Проверить У.] Если [У[ > 1 (переполнение дробной части), перейти к шагу Х4. Если У = О, установить е равным его наименьшему значению и перейти к шагу Х7. г12. [У нормализовано7] Если [У[ > 1/6, перейти к шагу Хб. ХЗ.
[Масштабировать, сдвинув влево.] Сдвинуть У на один разряд влево (т. е. умножить на Ь) и уменьшить е на 1. Возвратиться к шагу Х2. Х4. [Масштабировать, сдвинув вправо.] Сдвинуть У вправо на один разряд (т. е. разделить на Ь) и увеличить е на 1. Хб. [Округлить,] Округлить У до р разрядов. (Это означает, что У изменяется до ближайшего кратного Ь г.
Возможно, что (ЬгУ) шоб 1 = 1~, т. е. имеется деа ближайших кратных. Если 6 чегно, то заменяем У ближайшим кратным Ь г, таким, что ЬэУ' + эЬ нечетко (обозначим результат округлении в таком случае через У'). Более подробное обсуждение аспектов округления приводится в разделе 4.2.2.) Важно отметить, что операция округления может привести к равенству [У[ = 1 (переполнение при округлении); в такой ситуации следует вернуться к шагу Х4.
г16. [Проверить е.] Если порядок е слишком велик, т. е. больше допустимой границы, это воспринимается, как выполнение условия переполнения порядка. Если е слишком мал, это воспринимается, как выполнение условия исчезновения Рис. 3. Нормализация (е, 7). гюрядка. (Дополнительная информация по этому вопросу приводится ниже; этн ситуации интерпретируются обычно, как сигнал об ошибке, в том смысле, что результат не может быть представлен в виде нормализованного числа с плавающей точкой из требуемого интервала значений.) гчТ.
(Упаковать.) Объединить порядок е и дробную часть у для выдачи искомого результата. Несколько простых примеров сложения чисел с плавающей точкой рассматривается е упр. 4- Приведенные ниже подпрограммы для сложения н вычитания на компьютере ИХХ чисел, имеющих форму (4), служат примером программной реализации алгоритмов А и Х. Этн подпрограммы извлекают одно входное значение и по символическому адресу АСС, другое входное значение и извлекается из регистра А при входе в подпрограмму, Результат ю одновременно появляется в регистре А н в поле АСС. Таким образом, последовательность команд ЬРА А; АОВ В; ЗОВ С," БТА Э, работающих с числами с фиксированной точкой, соответствовала бы такой после- довательности команд, работающих с числами с плаватощей точкой: 10А А, ЗТА АСС; ЫА В, ЛИР ЕАИ); ЫА С, ЛИР РВОВ; ЯТА В.
(В) Программа А (Сложение, емчиглаиие и нормализация). Следующая программа представляет собой подпрограмму, реализуюшую алгоритм А, причем она построена таким образом, что нормализующий фрагмент может использоваться другими подпрограммами, которые будут рассмотрены ниже. Как в этой программе, так и во многих других программах данной главы, идентификатор ОГ1.0 именует подпрограмму, которая печатает сообщение о том, что индикатор переполнения машины Н1Х внезапно перешел в состояние "включено". Предполагается, что размер байта А кратен 4.
В подпрограмме нормализации МОНН предполагается, что г12 = е и гАХ = у, где гА = 0 влечет за собой гХ = О и г12 с Ь. гП +- -е„. 00 НУТЕ 01 ЕХР 08 ГЗОВ 08 01 ГАВО 08 07 08 09 10 11 13 18 Ц 16 1Н 16 17 18 4Н 80 ЗН 81 88 88 ЗН 81 86 86 87 88 80 80 81 88 84 88 86 87 НАЕГ 88 ГО 89 ГЧ ЕОО 1(4:4) ЕЦО 1:1 ЗТА ТЕМР (.ОАМ ТЕИР ЗТ1 ЕХТТГ 107 ОГ(.0 ЗТА ТЕИР (.ОХ АСС СИРА АСС(ЕХР) 80Е 1Г ЗТХ ГО(0:4) 002 АСС(ЕХР) ЗТА ГТ(0:4) 1.01М ТЕИР(ЕХР) ЛИР 4Г ЗТА ГО(О:4) (.02 ТЕИР(ЕХР) ЗТХ ГЧ(0:4) 1.01М АСС(ЕХР) ХМС1 0,2 (.ОА ГГ ЕИТХ 0 ЗНАХ 0,1 А00 ГО 307 М4 ЛХХ ИОЕИ СИРА О (1:1) ЯМЕ МЬ ЗНС б ОЕСХ 1 ЗТА ТЕИР ЗТА НА(.Г(0:О) 1.0АМ ТЕМР АОО НА(.Г АРО НА1.Г ЗНС 4 1НР ИВА СОМ 1О2 СОМ 0 СОМ 0 Размер байта Ь.
Определение поля порядка. Подпрограмма вычитания чисел с плавающей точкой, Изменить знак операнда. Подпрограмма сложения чисел с плавающей точкой. Снятие блокировки переполнения. ТЕМР +- е. гХ+- а. Шаги А1-А8 скомбянн вены нные. Переход, если е„> е„. РУ е- ж г г 1 1 О, г12~-е . РЮе- жуг /10 (а,е меняются ролями).
г12+- ея, гП+- -е„. гП +- е — е,, (П(аг А4 не является необходимым.) А6. Масштабу рвать н вп аво. Очистить гХ. Сдвиг вправо иа е„— е„позиций. Ай о~~ Аг. Ноума.чизм(йяж Переход, если произовгло переполнение. Простой случай? ?нормализовано? Если нормализовано, округлить его. ~гХ~ Фь ~гА~. (гХ положительно.) (Операнды имеют щютивоположные знаки; нужно уточнить состояние регистров перед округлением и нормализацией.) Дополнить наименьшей значащей величиной.
Переход к подпрограмме нормализации. Половина размера слова (знак может изменяться). Дробная часть 1 . Дробная часть /„. 60 ИОНН ,)АХ ХЕО 61 М2 СИРА О (1:1) 46 ЛИЕ Иб кьдкаккь Ю2. о мадизова лн Перейти к шагу ХЬ, если ведущий байт отличен от нуля, гГ . Масштабв ть . и в влево.
46 ИЗ 64 ИЗА 46 46 Н4 47 З(.АХ 1 ОЕС2 1 ЛМР И2 ЕИТХ 1 ЗЕС Уменьшить е на 1. Вернуться к шагу Н2. Х, ас и зать н вп аво Выполнить сдвиг вправо и вставить "Г с соответствующим знаком. Увеличить е на 1. КЙ Окйтгденяи15 )остаток) < ТЬТ )остаток! > АЬ? )остаток) = -Ь; округлить до нечетного. г12+- е — Ь.
Довольно большой фрагмент кода программы (строки 25-37) включен в программу по той причине, что в Н1Х имеется 5-байтовый аккумулятор для сложении чисел со знаком, в то время как алгоритм А в общем случае требует для него 2р+ 1 = 9 разрлдов. В действительности всю программу можно сократить почти вдвое, если пожертвовать хотя бы небольпюй долей точности. Однако, как будет показано в сведующем разделе, всегда лучше получать наибольшую возможную точность.
В строке 55 используется нестандартная команда Н1Х, описанная в разделе 4.5.2. Время выполнения сложения и вычитания чисел с плавающей точкой зависит от нескольких факторов, анализируемых ниже, в разделе 4.2.4. Рассмотрим теперь операции умножения н деления, которые выполняются проще, чем сложение, и довольно похожи одна на другую. Алгоритм М (Ужнолсеиие или деление чисел с плавающей точкой).
По данным р-разрядным нормализованным числам с плавающей точкой и = (ек,Ук) и с = (е,, ?к) по основанию Ь с избытком д строится произведение ш = и 6Ь с или частное ю = и ф Ф. М1. (Распаковать.) Выделить порядки и дробные части в представлениях и и с. 46 69 Иб 60 61 66 60 64 66 66 ЗН 67 66 О М6 60 И7 61 6к ХНО 60 ЗН 64 ЕХ1ТР 66 ЕХРОЧ 66 ЕХ РОМ 67 АСС 1ИС2 1 СИРА кВТТЕ/2 (5:5) 65 Нб )О ЗР )ХИХ ЗР ЗТА ТЕМР ЕОХ ТЕМР(4:4) )ХО М6 ЗТА к+1(0:О) 1ИСА В?ТЕ ЛОМ И4 62И ЕХРОН ЕИТХ 0,2 ЗНС 1 ОЕС2 В?ТЕ ЗТА АСС 62И НЕТ 2 Н1.Т 1 СОИ 0 Перейти к шагу Мб, если гХ нечетно, Остранить знак гА.
Добавить Ь а к Щ (знак может измениться) Проверить переполнение из-за округления. Акй,)Тйойейав е. Исчезновение порядка, если е < О. Ю. уккккк к Выход, если только не е > Ь. Обнаружено переполнение порядка, Обнаружено исчезновение порядка. Аккумулятор для операций с плавающей точкой. $ (Иногда удобно, хотя и необязательно, проверить в ходе выполнения этого шага, не равны лн операнды нулю.) М2. [Выполнить операцию.) Установить ем < ео + ек ф ум < ук /~ Длк Умнпжсинк; (О) е +- е„— е„+ д+ 1, у < — (6 '1„)1'у„для деления. (Поскольку преднолагаегся, что вводимые числа нормализованы, в результате получим, что либо 1„, = О, либо 1/62 < ~Я с 1, либо возникнет ошибка "деление на нуль".) Здесь, если в этом есть необходимость, можно урезать 1 до р+ 2 или р+ 3 разрядов, как в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
