что и следовало доказать. Если < р, должно оказаться, что ег,=р-Inw - ы кратно Ь~. Таким образом, результат будет совпадать с округленным значением, если его абсолютная величина меньше, чем Ь + Ь. Поскольку Ь < 3, мы, конечно же, получим \w-u\ < u;-u-7; + 7; < + (6-1 -61) < Ьр~ +Ь~. Таким образом, доказательство завершено.

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

Не существует правила округления на все случаи жизни. Например, обычно желательно иметь специальное правило для округления прибыли, облагаемой налогом. Но для большинства расчетов наилучшим следует считать предлагаемый в алгоритме 4.2.IN вариант, который "настаивает" на том, чтобы наименее значимый разряд был всегда четным (или всегда нечетным) в случаях, допускающих неоднозначность трактовки правил округления. Реализовать апп?1ратно такое правило - отнюдь не тривиальная задача. Однако существуют весьма серьезные практические соображения в пользу ее решения, поскольку такие неоднозначные ситуации часто возникают совершенно неожиданно и двойственное решение приводит к существенно отрицательным результатам. Например, рассмотрим действия в десятичной системе и будем считать, что остаток 5 всегда округляется в большую сторону. Тогда, если и - 1.0000000 и V = 0.55555555, получим и ® v = 1.5555556. Если в формате с плавающей точкой из этого результата вычесть v, то получится и = 1.0000001. Сложение и вычитание v из и дает 1.0000002, а в следующий раз получи.м 1.0000003 и т. д. Таким образом, результат будет постоянно увеличиваться, хотя складывается и вычитается одно и то же число.

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

Теорема D. (((и @ v) Q v) @ v) Q v = {и @ v) е v.

Например, если и = 1.2345679 иу = -0.23456785, то

u@v = 1.0000000, iu®v)ev = 1.2345678,

{iu®v)ev)®v = 0.99999995, {{{и @v)ev)®v)ev = 1.2345678.

Доказательство для любых ии v, как нам кажется, потребует еще более скрупулезного анализа частных случаев, чем в теоремах, рассмотренных выше (см. ссылки на литературу, которые приведены ниже).

Теорема D справедлива и в отношении "округленных до четного", и в отношении "округленных до нечетного", и возникает вопрос, какой же из вариантов выбрать. Когда основание системы счисления Ь нечетно, подозрительных случаев возникнуть не может, кроме как при делении в формате с плавающей точкой, а здесь округление, в общем-то, не имеет значения. Если же основание системы счисления

четно, есть смысл придерживаться следующего правила: "Округлять до четного, если 6/2 нечетно, и округлять до нечетного, если 6/2 четно". Наименее значимый разряд в дробной части числа в формате с плавающей точкой часто образуется в результате округления остатка при последовательно выполняемых операциях, и это правило позволяет, насколько это возможно, избежать формирования значения 6/2 в наименее значимом разряде. На практике применение этого правила приводит к тому, что выделяется некоторая память для подозрительных операций округления, чтобы последовательные округления имели тенденцию к формированию результата, не вызывающего неоднозначного толкования. Например, если округлять до нечетного в десятичной системе, повторяющиеся операции округления числа 2.44445 с "укорачиванием" на один разряд дадут результат в виде последовательности 2.4445, 2.445, 2.45, 2.5, 3; если же округлять до четного, подобные ситуации не возникнут, хотя повторяющееся округление чисел наподобие 2.5454 приведет к почти такой же ошибке. [См. Roy А. Keir, Inf. Proc. Letters 3 (1975), 188-189.] Иногда предпочтение отдается округлению до четного в любом случае, и в результате наименее значимый разряд оказывается равным О чаще. В упр. 23 продемонстрировано это преимущество округления до четного. Но, в конце концов, ни один из альтернативных вариантов не имеет решающего преимущества над другими. К счастью, обычно в качестве основания системы счисления используется 6 = 2 или 6 = 10, и тогда все согласны, что правило округления до четного является наилучшим.

Читатель, который заинтересуется деталями доказательства изложенных выше положений, обнаружит существенное упрощение задачи, которое предоставляет простое правило u®v = round(u--7;). Если бы подпрограмма сложения в формате с плавающей точкой не следовала этому правилу в любом, даже в самом редком, случае, доказательство стало бы существенно более сложным и, возможно, его вообще не удалось бы сформулировать.

Теорема В не выполняется, если вместо округления используется арифметическое "усечение", т. е. если положить u®v=- trunc(u + v) nuQv = trunc(u - v), где trunc(a:) для действительных положительных x есть наибольшее число в формате с плавающей точкой, которое < х. Исключение из теоремы В возникло бы, следовательно, в случаях, подобных (20,-f. 10000001) © (10, -.10000001) = (20,-Н.10000000), когда разность между и + уии®уне может быть точно выражена в виде числа в формате с плавающей точкой. Также исключением был бы случай, подобный 12345678® .012345678, если он может встретиться в практике решения конкретного круга вычислительных задач.

Многие думают, что, поскольку арифметика в формате с плавающей точкой неточна по самой своей природе, не будет никакой беды в том, чтобы, если это окажется удобным, в некоторых довольно редких случаях выполнять вычисления чуть менее точно. Такая политика сберегает несколько центов при проектировании аппаратуры компьютера или небольшую часть общего времени выполнения подпрограммы, но проведенный выше анализ показывает, что подобный подход ошибочен. Можно сэкономить до 5% времени выполнения подпрограммы FADD и программы 4.2.1А, а также около 25% занимаемого ими пространства в оперативной памяти, если позволить себе вольность и некорректно осуществить округление в редких случаях, но гораздо лучше оставить эти программы в прежнем виде. И дело здесь не в "погоне за битами"; на карту поставлено нечто более важное и фундаментальное:

полпрограммы работы с числами должны давать результаты, которые максимально удовлетворяют простым общепринятым математическим законам. Ключевая формула и ® V = round(u -I- v), например, выражает некое свойство "регулярности", и, таким образом, решается вопрос, стоит ли проводить математический анализ вычислительных алгоритмов. Не располагая какими-либо свойствами симметрии, составляющими фундамент дальнейших рассуждений, было бы крайне неудобно доказывать интересные результаты. Получать удовольствие от работы с привычным инструментом-это, конечно, одно из важнейших условий успешной работы.

В. Арифметические действия над ненормализованными числами с пла-в£1ющей точкой. К практике нормализации всех чисел в формате с плавающей точкой можно относиться двояко: либо благосклонно воспринимать ее как попытку получения максимально возможной точности, достижимой для данной разрядности, либо рассматривать ее как потенциально опасную политику в том смысле, что она "соблазняет" нас считать результаты более точными, чем есть на самом деле. Когда, нормализовав результат операции (1,-ь.31428571) 0 (1,-I-.31415927), мы получаем (-2, -Ь.12644000), теряется информация о возможно большей неточности результата. Такая информация сохранилась бы, если бы ответ остался в виде (1, -ь.00012644).

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

(27,+.00060221) и (-23,+.00066261),

а не через (24,+.60221400) и (-26,+.66261000). Было бы прекрасно, если бы можно было задавать входные данные для каждой задачи в ненормализованной форме, из которой можно было бы почерпнуть информацию об их реальной точности, и если бы в выходных данных содержалась информация о том, какова точность результата. К несчастью, это ужасно сложная проблема, хотя использование ненормализованной арифметики и может помочь получить некоторые сведения такого рода. Например, можно говорить с большой степенью уверенности, что произведение числа Авогадро и постоянной Планка равно (1,+.00039903), а их сумма равна (27,+.00060221). (Данный пример приведен не для того, чтобы привести к мысли о том, будто сумме или произведению этих фундаментальных констант можно приписать какой-либо важный физический смысл, а чтобы продемонстрировать, что можно сохранить некоторую информацию о точности результата вычислений над неточными величинами, когда исходные операнды не зависят один от другого.)

Правила ненормализованной арифметики просты: пусть - количество веду-. щих нулей в дробной части числа « = (€„,/„), так что 1и есть наибольшее целое число < р, для которого /и < b~. Тогда сложение и вычитание выполняются точно так, как в алгоритме 4.2.1А, но все сдвиги влево, масштабирующие дробную часть, опускаются. Умножение и деление выполняются так же, как в алгоритме 4.2.1М, но результат сдвинут вправо или влево, так что его дробная часть будет начинаться в точности с max(/u,/„) нулей. По существу, те же правила на протяжении многих лет использовались и для традиционных вычислений вручную.