Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 77
Текст из файла (страница 77)
24. [М27] Рассмотрим множество всех интервалов [щ, . О,], где щ и и есть либо отличные от нуля числа в формате с плавающей точкой, либо специальные символы +О, — О, +со, — сю. Каждый интервал должен иметь щ < и„и щ = и, допускается только при условии, что щ конечно и отлично от нуля. Интервал [щ .. и,] вмешдет все числах в формате с плавающей точкой, такие, что щ < х < и„причем, мы полагаем, что -Оо < -х < — О < +О < +х < +оо для всех возможных х. (Таким образом, [1..2] означает 1 < х < 2; [+О..1] означает О < х < 1; [-О ..
1] означает О < х < 1; [-О .. +О] представляет единственное значение О; [ — Оо .. +Со] вмещает все,) Покажите, как определить соответствующие арифметнче,'кис операции на всех этих интервалах, не принимая во внимание индикаторов переполнения или потери значимости, кроме как прн делении на число иэ интервала, содержащего нуль. ь 25. [12] Когда речь заходит о точности выполнения арифметических операций в формате с плавающей точкой, ошибки зачастую приписываются "отказам", которые возникают при вычитании близких по значению величин. Но, если и и е почти равны, разность и З е получается безо всяких Ошибок.
Что же тогда подразумевается под "отказами"? 26. [М21] Дано: и, и', е и с' — положительные числа в формате с плавающей точкой, причем и й (е) и с О' (с). Предполагая использование нормализованной арифметики, докажите, что существует малое значение е', такое, что и Ю с и' Ю О (е ). 27. [М27] (У. М. Кахан.) Докажите, что 1З (1З(1Зи)) ю 1 Зи для любых и Ф О. 28. [НМЯЦ (Г.
Дж. Диамонд (Н. С. П1ашош1).) Предположим, 1(х) есть жестко возрастающая функция на некотором интервале [хе .. х,], и пусть 2(х) — обратная ей функция, (Например, 1 и 2 могут быть "ехр" и "1п" или йап" и "агссав".) Если х — -число в формате с плавающей точкой, такое, что хо < х < х~ „то пусть 1(х) = гоппц(1(х)) и, если у — другое числО, такое, что 7(хе) < у < 1(х1), пусть 9(у) — тоивп(у(у)). Далее1 пусть а(х) = 2(1(х)), если только оно определено. Хотя а(х) и не всегда равно х нз-за округления, можно рассчитывать,что И(х) очень близко к х.
Докажите, что если точность Ье как минимум равна 3 и если у' — жестко вогнутая нли жестко выпуклая (т. е. 1' (х) имеет тот же знак для всех х, принадлежащих интервалу [хе, . х~]), то многократное применение л будет устойчиеилс в том смысле, что Ь(й(11(х))) = й(Ь(х)) ллв всех х, таких, что обе части этого равенства определены. Другими словами, не должно быть никакого "дрейфа", если подпрограмма правильно запрограммирована. «29. [М85) Приведите пример, чтобь» показать, что Ь«> 3 есть ншбхолимое условие для предыдущего упражнения.
«30 (М30) (У. М. Кахан.) Пусть у(х) ы 1+к+ .. +хин (1-х'егу(1-к) ллэ х < 1 и пусть 9(у) = »((э — у )(3+ 3459~)) при 0 < у < 1. Вмчнслите 9(П) иа разнмх карманных кэлькуляторахдля у= 10 э, 10», 10», 10 е нобъясните, почему все результатм, которые при этом получены, различны. (Поскольку в большинстве современных кьэькуляторов округление выполняется неправильно, результаты могут стать лля вэс большим сюрпризом. Обратите внимание, что д(») = 107 — 10491.35»э + 659749.9625»~ — 30141386.26625»~ + 0(»э).) 31. (МЯ5) (У. Кулиш (П.
КпИэсЬ).) При вычислении полинома 29~ + 9х» — у» для х = 408855776 и и = 708158977 с использованием стандартного пакета подпрограмм арифметики с плавающей точкой с двойной точностью (53 бит) получен результат ш -3.7 х 10'~. Вычисление по альтернативной формуле 2уэ + (Зкэ — у~)(Зхэ+ у ) дает - +1.0 х 10'э. Правильный ответ, однако,— точно 1.0. Объясните, как строить аналогичные примеры нестабильности вычислений. «4.2.3. Вычисления с удвоенной точностью Да сих пор речь шла об арифметических операциях над числами с однократной точностью в формате с плавающей точкой.
Эта, па существу, означает, чта числа в формате с плавающей точкой, с которыми мы имели дело, могли храниться в одном машинном славе. Если вычисления и таком формате не обеспечивают достаточной для приложения точности, ее можно увеличить программными средствами, используя для представления каждого числа два или больше слов памяти.
Хотя проблема вычислений с высокой точностью будет в общем виде рассмотрена в разделе 4.3, имеет смысл отдельно проанализировать возможности формата с удвоенной точностью представления. Специальные методы, которые используются при работе с таким форматом, практически непригодны для большей точности. Кроме того, вычисления с удвоенной точностью разумно считать темой, имеющей самастоятельяае значение, так как это первый шаг за пределы однократной точнастн и, работая в этом формате, можно удовлетворительна решать многие задачи, не требующие чрезвычайно высокой точности.
54атернал настоящего раздела был актуален, когда автор работаз нэд пер- Ф вым изданием этой книги в начале. бО-х годов. На с тех пор компьютеры были значительно усовершенствованы и причины, па которым использовались операц»ги с удвоенной точностью, ушли в прошлое. Таким образам, на сегодняшний день данный материал представляет скорее исторический интерес. В планируемом четвертом издалпя этой книги раздел 4.2Л будет называться "Нормализованные вычисления", а в настоящем разделе, 4.2.3„будут рассматриваться "необычные числа". В новой редакции данного раздела внимание будет сосредоточено на специфических аспектах стандарта АНЯ/»ЕЕЕ Яап»)аг»( 754» представлении необычных числовых величин наподобие бесконечности н неопределенности (так называемых Ха№).
(См. ссылки на литературу в конце раздела 4.2.1.) Тем не менее давайте все-таки бросим последнпй взгляд на идея, которые кажутся устаревпшмн, хотя бы для того, чтобы извлечь нз ннх урок на бу1»ушее. Арифметические операции с удвоенной точностью требуются чаще всего прн работе с чнгдамн в формате с плавающей точкой н значительно реже — при работе с числами в формате с фиксированной точкой. Исключением является, пожалуй, лишь область статистических расчетов, в которой для вычнслення сумм квадратов н перекрестных пронзведений обычно используются числа с фнкснрованной точкой н имеет смысл выполнять операции с удвоенной точностью.
Поскольку вычисления с удвоенной точностью для чисел с фиксированной точкой проще, чел1 с плавающей, наш аналнз будет ограничен этим последним случаем. Удвоенная точность очень часто желательна для увеличения не только точностн дробных частей чисел в формате с плавающей точкой, но и интервала изменения порядка, Таким образом, в этом разделе речь пойдет о следующем двухсловном представлении чисел с плавающей точкой в компьютере й1Х: Здесь используются 2 байта для хранения порядка и 8 байт для дробной части. Порядок имеет избыток Ьт(2, где о — размер байта.
Знак находится в слове, содержащем более значимые разряды; знак другого слова принято полностью игнорировать. Наш анализ арифметики с удвоенной точностью будет в значительной степени машинно-ориентированным, потому что, только рассматривая задачи, которые возникают при разработке программ, можно правильно воспринять предмет. Поэтому для понимания данного раздела важно внимательно изучить прнводнмые ниже программы для й1Х. Здесь мы постараемся "отдалиться" от идеалистических целей достижения точности, продекларированных в двух предыдущих разделах; рассматриваемые ниже процедуры ме екдючаюгп округления результатов н допускают наличие некоторой ошибки. Пользователи не рискуют слишком уж доверять такого рода подпрограммам.
Существуют весьма основательные причины блокировать все возможные нсточннкн ошибок прн вычнсленнях с однократной точностью, но теперь мы сталкиваемся с иной ситуацией, н вот почему. (а) Дополнительные фрагменты программ, требующиеся для обеспечения правнльностн округлення во всех случаях, довольно объемны, так что, скажем, программа, реализующая такой алгоритм, занимала бы раза в два больше места н требовала бы для выполнения раза в полтора больше времени. Сравнительно легко можно разработать прекрасные программы для вычисления с однократной точностью, но прн вычислениях с удвоенной точностью лицом к липу мы сталкнваемся с ограниченными возможностямн компьютерове. Аналогичная ситуация возникает н в отношении других подпрограмм, выполняющих вычнслення в формате с плавающей точкой. Нельзя ожидать от подпрограммы вычисления косинуса определения точного значе~ня гоппд(сов х) для всех х„поскольку это фактически невозможно, Вместо этого подпрограмма вычисления косинуса должна выдавать наименьшую возможную относительную ошибку прн всех возможных значениях х, которую можно получить за разумное время вычисления.
Конечно, программист должен стараться насколько зто возможно обеспечить выполнение математических * Автор, очевидно, имеет в виду компьвтерм — современники первого издания этой книги.— Лрнм. персе. законов, существующих в отношении вычисляемых функций, например (соз) (-х) = (соз) х; ! (со~э х) < 1; (соз) х > (соз) о при О < х < у < к, (Ь) Программы вычислений с однократной точностью — это "хлеб насущный" на каждый день, который должен быть доступен каждому, кто хочет работать с арвфметикой с плавающей точкой.
А удвоенная точность обычно используется в ситуациях, когда "чистые" результаты не так уж и важны. Разница между вычислениями с семью или восемью значащими разрядами достаточно заметна, а разница между вычислениями с 15 или 1б разрядами нас не очень беспокоит. Вычисления с удвоенной точностью чаще всего используются на промежуточных этапах решения сложной задачи с однократной точностью, а потому в полном спектре возможностей таких процедур нет необходимости. (с) Весьма поучительно проанализировать эти процедуры с тем, чтобы увидеть, насколько серьезной может быть ошибка„поскольку источники ошибок типичны и для "плохих" подпрограмм, работающих с однократной точностью (см. Упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
