в том случае, когда результат операции в формате с плавающей точкой округлен не очень аккуратно, при единственном предположении, что каждая операция дает ограниченную относительную ошибку.]

20. [25] (С. Линненмаа (S. Linnainmaa).) Найдите все и и v, для которых и > а соотношение (47) не выполняется.

21. [MS5] (Т. Дж. Деккер (Т. J. Dekker).) Теорема С показывает, как выполнить "точное" сложение чисел в формате с плавающей точкой. Покажите, как выполнить "точное" умножение чисел в формате с плавающей точкой: выразите произведение uv в форме W + w, где го и го вычислены на основе заданных чисел в формате с плавающей точкой и и V с использованием только операций ф, 0 и ®.

22. [Af,yO] Может ли возникнуть дрейф при умножении и/или делении в формате с плавающей точкой? Рассмотрите последовательность ю = и, X2n+i = Х2п ® v, Х2п+2 = X2n+i 0 v при заданных и и v ф 0. Каково значение наибольшего индекса к, при котором возможно выполнение условия Хк ф х*+2?

► 23. [AfSff] Докажите или опровергните следующее утверждение: для всех чисел и в формате с плавающей точкой справедливо равенство и 0 (и (mod) 1) = \ и\.

24. [М27] Рассмотрим множество всех интервалов [щ .. Ur], где щ и Ur есть либо отличные от нуля числа в формате с плавающей точкой, либо специальные символы -t-0, -О, -t-oo, -оо. Каждый интервал должен иметь щ < Ur, п щ = Ur допускается только при условии, что и/ конечно и отлично от нуля. Интервал [щ .. Ur] вмещает все числа х в формате с плавающей точкой, такие, что щ < х < Ur, причем, мы полагаем, что

-оо < -I < -О < +0 < +1 < +00

для всех возможных х. (Таким образом, [1.. 2] означает 1 < х < 2; [+0.. 1] означает О < X < 1; [-0.. 1] означает О < х < 1; [-0. .-t-0] представляет единственное значение 0; [-оо ..-t-oo] вмещает все.) Покажите, как определить соответствующие арифметические операции на всех этих интервалах, не принимая во внимание индикаторов переполнения или потери значимости, кроме как при делении на число изинтервала, содержащего нуль.

► 25. [15] Когда речь заходит о точности выполнения арифметических операций в формате с плавающей точкой, ошибки зачастую приписываются "отказам", которые возникают при вычитании близких по значению величин. Но, если и и v почти равны, разность и Q v получается безо всяких ошибок. Что же тогда подразумевается под "отказами" ?

26. [AfSi] Дано: и, и, V и v-положительные числа в формате с плавающей точкой, причем и ~ и (б) и и ~ и (е). Предполагая использование нормализованной арифметики, докажите, что существует малое значение б, такое, что и ф и ~ и ф и (б).

27. [М27] (У. М. Кахан.) Докажите, что 1 0 (1 0 (1 0 и)) = 1 0 и для любых ифО.

28. [НМЗО] (Г. Дж. Диамонд (Н. G. Diamond).) Предположим, /(х) есть жестко возрастающая функция на некотором интервале [хо . .xi], и пусть (х) - обратная ей функция. (Например, /ид могут быть "ехр" и "In" или "tan" и "arctan".) Если х-число в формате с плавающей точкой, такое, что хо < х < xi, то пусть /(х) = round(/(x)) и, если у-другое число, такое, что /(хо) < у < /(xi), пусть д{у) - round(5(y)). Далее, пусть h(x) = g(f(x)), если только оно определено. Хотя h(x) и не всегда равно х из-за округления, можно рассчитывать, что h{x) очень близко к х.

Докажите, что если точность Ь как минимум равна 3 и если / - жестко вогнутая или жестко выпуклая (т. е. /"(х) имеет тот же знак для всех х, принадлежащих интервалу [хо . .Xl]), то многократное применение h будет устойчивым в том смысле, что

h{h{h(x))) = h{h{x))

для всех x, таких, что обе части этого равенства определены. Другими словами, не должно быть никакого "дрейфа", если подпрограмма правильно запрограммирована.

► 29. [М25] Приведите пример, чтобы показать, что f > 3 есть необходимое условие для предыдущего упражнения.

► 30. [МЗО] (У. М. Кахан.) Пусть /(х) = 1 + х + • • • + х""* = (1 - х)/(1 - х) для х < 1 и пусть д(у) = /(( - у)(3 + 3.45у)) при О < у < 1. Вычислите д{у) на разных карманных калькуляторах для у = 10~, 10~*, 10"*, 10~ и объясните, почему все результаты, которые при этом получены, различны. (Поскольку в большинстве современных калькуляторов округление выполняется неправильно, результаты могут стать для вас большим сюрпризом. Обратите внимание, что д(е) = 107 - 10491.35б + 659749.9625б - 30141386.26625б + 0(е).)

31. [М25] (У. Кулиш (U. Kulisch).) При вычислении полинома 2у + 9х* - у* для х = 408855776 и у = 708158977 с использованием стандартного пакета подпрограмм арифметики с плавающей точкой с двойной точностью (53 бит) получен результат sa -3.7 х 10*. Вычисление по альтернативной формуле 2у -t- (Зх - у)(3х-t-у) дает и -t-1.0 х 10*. Правильный ответ, однако, - точно 1.0. Объясните, как строить аналогичные примеры нестабильности вычислений.

*4.2.3. Вычисления с удвоенной точностью

До сих пор речь шла об арифметических операциях над числами с однократной точностью в формате с плавающей точкой. Это, по существу, означает, что числа в формате с плавающей точкой, с которыми мы имели дело, могли храниться в одном машинном слове. Если вычисления в таком формате не обеспечивают достаточной для приложения точности, ее можно увеличить программными средствами, используя для представления каждого числа два или больше слов памяти.

Хотя проблема вычислений с высокой точностью будет в общем виде рассмотрена в разделе 4.3, имеет смысл отдельно проанализировать возможности формата с удвоенной точностью представления. Специальные методы, которые используются при работе с таким форматом, практически непригодны для большей точности. Кроме того, вычисления с удвоенной точностью разумно считать темой, имеющей самостоятельное значение, так как это первый шаг за пределы однократной точности и, работая в этом формате, можно удовлетворительно решать многие задачи, не требующие чрезвычайно высокой точности.

Материал настоящего раздела был актуален, когда автор работал над пер- L вым изданием этой книги в начале 60-х годов. Но с тех пор компьютеры были значительно усовершенствованы и причины, по которым использовались операции с удвоенной точностью, ушли в прошлое. Таким образом, на сегодняшний день данный материал представляет скорее исторический интерес. В планируемом четвертом тдании этой книги раздел 4.2.1 будет называться "Нормализованные вычисления", а в настоящем разделе, 4.2.3, будут рассматриваться "необычные числа". В новой редакции данного раздела внимание будет сосредоточено на специфических аспектах стандарта ANSI/IEEE Standard 754: представлении необычных числовых величин наподобие бесконечности и неопределенности (так называемых NaNs). (См. ссылки на литературу в конце раздела 4.2.1.) Тем не менее давайте все-таки бросим последний взгляд на идеи, которые кажутся устаревшими, хотя бы для того, чтобы извлечь из них урок на будущее.

Арифметические операции с удвоенной точностью требуются чаще всего при работе с числами в формате с плавающей точкой и значительно реже - при работе с числами в формате с фиксированной точкой. Исключением является, пожалуй, лишь область статистических расчетов, в которой для вычисления сумм квадратов и перекрестных произведений обычно используются числа с фиксированной точкой и имеет смысл выполнять операции с удвоенной точностью. Поскольку вычисления с удвоенной точностью для чисел с фиксированной точкой проще, чем с плавающей, наш анализ будет ограничен этим последним случаем.

Удвоенная точность очень часто желательна для увеличения не только точности дробных частей чисел в формате с плавающей точкой, но и интервала изменения порядка. Таким образом, в этом разделе речь пойдет о следующем двухсловном представлении чисел с плавающей точкой в компьютере MIX:

Здесь используются 2 байта для хранения порядка и 8 байт для дробной части. Порядок имеет избыток Ь/2, где Ь - размер байта. Знак находится в слове, содержащем более значимые разряды; знак другого слова принято полностью игнорировать.

Наш анализ арифметики с удвоенной точностью будет в значительной степени машинно-ориентированным, потому что, только рассматривая задачи, которые возникают при разработке программ, можно правильно воспринять предмет. Поэтому для понимания данного раздела важно внимательно изучить приводимые ниже программы для MIX.

Здесь мы постараемся "отдалиться" от идеалистических целей достижения точности, продекларированных в двух предыдущих разделах; рассматриваемые ниже процедуры не включают округления результатов и допускают наличие некоторой ошибки. Пользователи не рискуют слишком уж доверять такого рода подпрограммам. Существуют весьма основательные причины блокировать все возможные источники ошибок при вычислениях с однократной точностью, но теперь мы сталкиваемся с иной ситуацией, и вот почему.

(а) Дополнительные фрагменты программ, требующиеся для обеспечения правильности округления во всех случаях, довольно объемны, так что, скажем, программа, реализующая такой алгоритм, занимала бы раза в два больше места и требовала бы для выполнения раза в полтора больше времени. Сравнительно легко можно разработать прекрасные программы для вычисления с однократной точностью, но при вычислениях с удвоенной точностью лицом к лицу мы сталкиваемся с ограниченными возможностями компьютеров*. Аналогичная ситуация возникает и в отношении других подпрограмм, выполняющих вычисления в формате с плавающей точкой. Нельзя ожидать от подпрограммы вычисления косинуса определения точного значения round(cosa;) для всех х, поскольку это фактически невозможно. Вместо этого подпрограмма вычисления косинуса должна выдавать наименьшую возможную относительную ошибку при всех возможных значениях х, которую можно получить за разумное время вычисления. Конечно, программист должен стараться насколько это возможно обеспечить выполнение мате.матических

* Автор, очевидно, имеет в виду компьютеры - современники первого издания этой книги. - Прим. перев.