Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 69
Текст из файла (страница 69)
5. МЗ. (Нормализовать.) Применить к (е„, ум) алгоритм Н с тем, чтобы нормализовать, округлить и упаковать результат. (Замечание, В этом случае нормализация выполняется проще ввиду того, что масштабирование посредством сдвига влево происходит не более одного раза и после деления переполнение не может возникнуть вследствие округления.) $ В подпрограммах для И1Х, тексты которых приведены ниже, используются те же соглашения, что и в программе А. Этн подпрограммы служат примером машинной реализации алгоритма М. Программа М (Умнооюение и деление чисел с плаааюи1ей точкой). г12+- е„+ ек — Ч.
г12 <- е„ вЂ” е„ + Ч. гА+-1 . 01 Ц 02 РИО(, 08 04 дд дб 07 08 00 1д 11 10 12 Р01Ч Ц 1Ю 16 17 10 10 20 21 Ей йу 24 йд йб ЕЦО ЕТТЕ/2 БТ) ЕХ1ТР ЛОЧ ОРЕО БТА ТЕИР ьОХ АСС БТХ РО(0:4) 1.01 ТЕИР(ЕХР) 1.02 АСС(ЕХР) 1ИС2 -0,1 Б1.А 1 ИО(. РО ЛИР ИОЕИ БТЛ ЕХ1ТР 10Ч ОР10 БТА ТЕИР БТА РЧ(0:4) 1.01 ТЕИР(ЕХР) 1.02 АСС(ЕХР) ОЕС2 -Я, 1 ЕИТХ 0 ЫА АСС БЕА 1 СИРА РЧ(1:б) ЛЕ я+3 ЗЕА 1 ХИС2 1 Ч есть половина размера байта. Подпрограмма умножения чисел с плавающей точкой.
Снятие блокировки переполнения. ТЕКР ~ ь. гХ+- и. РО -~УШО. Умножить у„на 1 . Нормализовать., округлить к выйти кз подпрограммы. Подпрограмма деления чисел с плавающей точкой. Снятие блокировки переполнения. ТБИР+- е. РЧ+- х11110. Переход, если )У„~ ( ~У.~. Иначе — масштабировать у„вправо и увеличить г12 ва 1. гт 01Ч РЧ ЕУ 1ИОЧ ИОЕИ 39 ОЧХЕО НЬТ 3 Разделить.
Нормализовать, округлить и выйти из подпрограммы. Неиормвлиэоэано или делитель равен нулю. 1 Наиболее интересная особенность этой программы — подготовка к выполнению деления, осуществляемая командами в строках 23-26. Зги операции проводятся для того, чтобы обеспечить достаточиую точность при округлении ответа. При (~„~ < Щ, непосредственно применив алгоритм М, можно сохранить результат в форме ь~0,(7~,(" в регистре А, что сделает невозможным чистое округление без специального анализа остатка (он хранится в регистре Х). Поэтому в такой ситуации программа вычисляет 1 .
~- ~„/~г, гарантируя, что ~„, либо равно нулю, либо во всех случаях иормглизовано. Процедура округления может оперировать пятью значащими байтами, возможно, проверяя, ие равен ли остаток нулю. Иногда может потребоваться перевод из представления с фиксироваиной точкой в представление с плавающей точкой и обратно. При полющи описанного выше алгоритма иормализации легко получается программа перевода "из фиксированной в плавающую". Например, целое число переводится в форму с плавающей точкой с помощью следующей подпрограммы иа языке И1Х. О1 РЬОТ БТЛ ЕХ1ТГ Предполагаем, что гА ~ и есть целое число. ОЕ 10Ч ОРЬО Снятие блокировки переполнения.
ау ЕМТ2 0+6 Устаиовить "грубый" порядок. 04 ЕИТХ 0 Ов ЛИР ИОКИ Нормализовать, округлить и выйти из подпрограммы. $ (10) Подпрограмма перевода "из плавающей в фиксированную" служит предметом упр. 14. Отладка подпрограмм выполнения арифметцческих операций над числами с плавающей точкой — обычно довольно (ложная задача из-за обилия различных случаев, которые иужно предусмотреть. Ниже перечислены распростраиеииые ловушки, подстерегающие программиста, который занимается программами "плавающей арифметики".
1) Пбглерл знака. Во многих машинах (к И1Х зто не относится) команды сдвига регистров воздействуют на знаковый разряд, поэтому следует подробио анализировать операции сдвига, используемые при нормализации и изменении масштаба дробпой части числа. Часто зиак теряется и при появлении "минус нуля". (Например, операторы 30-34 программы А ответственны за установку знакового разряда регистра А.
См. также упр. 6.) 2) Невозможность правильного определения, чою произошло — исчегиввенив или переполнение порядка, Не счедучт проверять величину е до окончания операций округления и иормализации, так как предварительиые проверки могут привести к ошибочным результатам. Исчезновение и переполнение порядка могут происходить и при выполпеиии сложения и вычитания, а не только при умножении и делении, и, несмотря на то что зто событие довольно редкое„проверку необходимо проводить для каждого конкретного случая.
Для того чтобы выполнить необходимые корректирующие операции после обнаружения исчезновения или переполнения, нужно заранее позаботиться о сохранении достаточной для этого информации. К сожалению, некоторые программисты во многих случаях пренебрегают исчез- новением порядка. Они просто полагают, что исчезающе малые результаты равны нулю без индикации ошибки. Часто зто приводит к серьезной потере точности (а на самом деле к потере всех значаших цифр), что нарушает соглашения, при- нятые в операциях над числами с плавающей точкой.
Таким образом, системная подпрограмма действительно должна информировать прикладного программиста об исчезновении порядка. Прнравниванне результата к нулю допустимо только в отдельных случаях, когда результат должен складываться со значительно большей величиной. Если исчезновение порядка не фиксируется, то возникают таинственные ситуации, когда (и З р) З ш равно нулю, а и З (р З ш) нет, поскольку, скажем, умножение и З р приводит к исчезновению порядка, а и З (е З ш) вычисляется и без выхода порядков за пределы допустимого интервала. Подобным же образом можно найти пять таких положительных чисел а, Ь, с, д и у, что (а Зу йг Ь) З (сЗу ш с() лв -, (11) (а б) ЬЕ у) З (с Е Иву) = 1, если исчезновение порядка не фиксируется (см.
упр. 9). Даже с учетом того, что подпрограммы арифметики с плавающей точкой не идеально точны, такие несуразные результаты, как (11), совсем уж неожиданны для случая, когда все числа а, Ь, с, а и у нолоэгсишельны! Исчезновение порядка обычно не предугадывается программистом, так что ему следует об этом сообшатье. 3) Попадание "мусора". При выполнении сдвига влево необходимо проследить, чтобы в освобождающиеся разряды справа не было введено чего-либо, отличного от нулей.
Например, обратите внимание па команду ЕИТХ О в строке 21 программы А и Яслишком легко забываемую" команду ЕЕТХ О в строке 04 подпрограммы Р1ОТ в (10), (Но было бы ошибкой очищать регистр Х после строки 27 в подпрограмме деления.) 4) Непредусыопзренное переполнение цри округлении. Когда чисто наподобие .999999997 округляется до 8 цифр, происходит перенос влево от десятичной точки н результат сдвигается вправо. Многие ошибочно считали, что в ходе выполнения * С другой стороны, нужно отметить, что современные языки программирования высокого уровня предоставляют программисту (или вовсе не предогтаяляют) весьма огрвниченные возможности использования ин4юрмвции, содержащейся в ствндвртнмх программах врифметикн с плвввющей точкой.
Подпрограммы для И11, которые предстевлены в этом разделе, просто остэнввлявв ют работу, обнаружив такую ситуацию, в это отнюдь не выход. Существует множество приложе. ний, для которых исчезновение порядкв относительно безвредно, и потому желательно найти спо. соб, пользуясь которым прогрвммист смог бы просто н безопвсво для приложения спрввиться с возникшей проблемой. Практика подстввовки "втихомачку" нуля вместо резучьтлта с исчезнувшим порядком себя полностью дискредятироввлв, но существует ельтернвтивв, которая в последнее время зввоевывэет все большую популярность. Ее суть в том, чтобы модифицироввть самое определение формата предстввления чисел с плвввющей точкой, допусивя существовение ненормалнзовэнной дробной части в случае, если порядок имеет минимвльное допустимое знвчение.
Этв идея "ппстепениой потери зивчимости" впервые была реыигзоввнв в компьютере Е!ее!го!об!св ХВ! онв лишь незнвчительно усложнилв элгорятмы выполнения опервций, но совершенно исключила возможность исчезновения порядкв при сложении и вычитании. Рвссмотреиие этой идеи выходит ээ рамки данной книги, поэтому в простых формулах анализа относительной ошибки вычислений в рвэкеле 4.2.2 появление постепенной потери знвчнмости не учитывается. Тем не менее, используя формулы, подобные гопы!(х) = х(1 — 6) + с, где )6! < 6' г/2 и )г) ( 6 г е/2, можно показать, что 4юрмвт с постепенной потерей знвчимости успешно сребвтыввет во многих важных случаях. (См.
Ъг', М. Квэвп эпб Л. Рв1шег, ЛСМ ИСЬ ПМ ггежв!егсег (Ос!оьег, 1979), 13-21.) умножения переполнение при округлении невозможно, так как максимальное значение ]~„Я равно 1 — 2Ь я+Ь з", а это число не может округлиться до 1. Ошибочность такого рассуждения продемонстрирована в упр, 11. Любопытно„что переполнение при округлении действительно невозможно при делении чисел с плавающей точкой (см. упр. 12). Существует направление, представители которого утверждают, что можно безболезненно "округлять" .999999997 до .99999999, а не до 1.0000000, поскольку последний результат представляет все числа из интервала (1.0000000 — 5 х 10 г ., 1.0000000+ 5 х 10 е], в то время как .99999999 представляет все числа из гораздо меньшего интервала ( 99999999 — 5 х 10 в 99999999+ 5 х 10 г) Хотя второй интервал и не содержит исходного числа .999999997, каждое число из второго интервала содержится в первом, так что последующие вычисления со вторым интервалом не менее точны, чем с первым, Но зтот довод несовместим с математической идеологией арифметики с плавакнцей точкой, представленной ниже, в разделе 4.2.2.
5) Округление дв нормализации. Неточность результата порождается и преждевременным округлением в неверных цифровых разрядах. Эта ошибка очевидна, когда округление производится слева от соответствующего разряда. Она также опасна в менее очевидном случае, когда округление сначала выполняется намного правее, а затем--в истинном разряде. По этой причине ошибочно осуществлять округление в ходе операции "сленг вправо" на шаге Ао; исключением является случай, рассмотренный в упр. 5, (Однако специальный случай округления на шаге Н5, а затем повторного округления уже после переполнения при округлении безобиден, потому что переполнение при округлении всегда приводит к значению ~1.0000000, которое ве меняется в результате последующей процедуры округления,) б) Невозможность сохранения достаточной точности в промежуточных вычисленная. Детальный анализ точности арифметических операций с плавающей точкой, проводимый в следующем разделе, показьвает, что нормалнзующие программы арифметики с плавающей точкой должны всегда обеспечивать максимальную точность подходящим образом округленного результата.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
