Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 74
Текст из файла (страница 74)
Не существует правила округления на все случаи жизни. Например, обычно желательио иметь специальное правило для округления прибыли, облагаемой налогом. Но для большинства расчетов наилучшим следует считать предлагаемый в алгоритме 4.2.1Х вариант, который "настаивает" на том, чтобы наименее значимый разряд был всегда четным (или всегда нечетным) в случаях, допускающих неоднозначность трактовки правил округления. Реализовать аппаратно такое правило— отнюдь ие тривиальная задача. Однако существуют весьма серьезные практические соображения в пользу ее решения, поскольку такие неоднозначные ситуации часто возиикают совершенно неожиданно и двойственное решение приводит к существеино отрицательным результатам.
Например„рассмотрим действия в десятичной системе и будем считать, что остаток 5 всегда округляется в ббльшую сторону. Тогда, если и = 1.0000000 и е = 0.55555555, получим и В е = 1.5555556. Если в формате с плавающей точкой из зтого результата вычесть е, то получится и' = 1.0000001. Сложение и вычитание е из и' дает 1.0000002, а в следующий раз получим 1.0000003 и т. д. Таким образом, результат будет постоянно увеличиваться, хотя складывается и вычитается одно и то же число.
Это явление, называемое дрейфам, не возникнет, если использовать стабилизирующее правило округления, базирующееся на приоритете наименее зиачимого разряда. Теорема О. (((иЬе) бе) бе) Эе = (иЬе) бе. Например, если и = 1.2345679 и е = -0.23456785, то и б е = 1.0000000, (и Ы е) О е = 1.2345678, ((и ш е) 9 е) 9 е = 0.99999995, (((и Е е) В е) Е е) В е = 1.2345678. Доказательство для любых и и е, как иам кажется, потребует еще более скрупулезиого анализа частных случаев, чем в теоремах, рассмотренных выше (см. ссылки иа литературу, которые приведены ниже).
$ Теорема В справедлива и в отношении "округленных до четного", и в атношении "округленных до нечетного", и возникает вопрос, какой же из вариантов выбрать. Когда основание системы счисления 6 иечетно, подозрительных случаев возникнуть ие может, кроме как при делении в формате с плавающей точкой, а здесь округление, в общем-то, не имеет значения.
Если же основание системы счисления чеглио, есть смысл придерживаться следующего правила: "Округлять до четного, если 5/2 нечетно, и округлять до нечетного, если 5/2 четно", Наименее значимый разряд в дробной части числа в формате с плавающей точкой часто образуется в результате округления остатка при последовательно выполняемых операциях, и это правило позволяет, насколько это возможно, избежать формирования значения Ь/2 в наименее значимом разряде.
На практике применение этого правила приводит к тому, что выделяется некоторая память для подозрительных операций округления, чтобы последовательные округления имели тенденцию к формированию результата, не вызывающего неоднозначного тачкования. Например, если округлять до нечетного в десятичной системе, повторяющиеся операции округления числа 2.44445 с "укорачиванием" на один разряд дадут результат в виде последовательности 2.4445, 2.445, 2.45, 2.5, 3; если же округлять до четного, подобные ситуации не возникнут, хотя повторяющееся округление чисел наподобие 2.5454 приведет к почти такой же ошибке. )См.
Ноу А. Кениг, 1пг". Ргос. 7 еггегэ 3 (1975), 188 — 189.] Иногда предпочтение отдается округлению до четного в любом случае, и в результате наименее значимый разряд оказывается равным 0 чаще. В упр. 23 продемонстрировано это преимущество округления до четного. Но, в конце концов, ни один из альтернативных вариантов не имеет решающего преимущества иад другими. К счастью, обычно в качестве основания системы счисления используется 5 = 2 или 5 = 10, и тогда все согласны, что правило округления до четного является наилучшим. Читатель, который заинтересуется деталями доказательства изложенных выше положений, обнаружит существенное упрощение задачи, которое предоставляет простое правило и бе = гоппо1и+ э).
Если бы подпрограмма сложения в формате с плавающей точкой не следовала этому правилу в любом, даже в самом редком, случае, доказательство стало бы существенно более сложным и, возможно, его вообще не удалось бы сформулировать. Теорема В не выполняется, если вместо округления используется арифметическое "усечение", т. е. если положить и 9 э ж Фгцпс(и + э) и и Э в = Фгипс1и — э), где тгипс(х) для действительных положительных х есть наибольшее число в формате с плавающей точкой, которое < х. Исключение из теоремы В возникло бы, следовательно, в случаях, подобных 120, +.10000001) 9 (10, —.10000001) = ~20, +.10000000), когда разность между и + э и и Э э не может быть точно выражена в виде числа в формате с плавающей точкой.
Также исключением был бы случай, подобный 123456789,012345678, если он может встретиться в практике решения конкретного круга вычислительных задач. Многие думают, что, поскольку арифметика в формате с плавающей точкой неточна по самой своей природе, не будет никакой беды в том, чтобы, если это окажется удобным, в некоторых довольно редких случаях выполнять вычисления чуть менее точно. Такая политика сберегает несколько центов при проектировании аппаратуры компьютера или небольшую часть общего времени выполнения подпрограммы, но проведенный выше анализ показывает, что подобный подход ошибочен. Можно сэкономить до 5% времени выполнения подпрограммы Рапп и программы 4.2.1А, а также около 25% занимаемого ими пространства в оперативной памяти, если позволить себе вольность и некорректно осуществить округление в редких случаях, но гораздо лучше оставить эти программы и прежнем виде.
И дело здесь не в "погоне за битами"; на карту поставлено нечто более важное и фундаментальное: подпрограммы работы с числами должны давать результаты, которые максимально удовлетворяют простым общепринятым математическим законам. Ключевая формула и ф е = гоипб(и+ е), например, выражает некое свойство "регулярности", и, таким образом, решается вопрос, стоит ли проводить математический анализ вычислительных алгоритмов. Не располагая какими-либо свойствами симметрии, составляющими фундамент дальнейших рассуждений, было бы крайне неудобно доказывать интересные результаты.
Получать удовольствие от работы с привычным инструментом — это, конечно„одно из важнейших условий углешной работы. В. Арифметические действия над ненормализованными числами с плавающей точкой. К практике нормализации всех чисел в формате с плавающей точкой можно относиться двояко; либо благосклонно воспринимать ее как попытку получения максимально возможной точности, достижимой для данной разрядности, либо рассматривать ее как потенпиально опасную политику в том смысле, что она "соблазняет" нас считать результаты более точными, чем есть на самом деле.
Когда, нормализовав результат операции (1, +.31428571) О (1,+.31415927), мы получаем ( — 2, +,12644000), теряется информация о возможно большей неточности результата. Такая информация сохранилась бы, если бы ответ остался в виде (1, +.00012644). При решении любой задачи, связанной с вычислениями, часто оказывается, что входные данные известны с точностью, меньшей, чем точность, обеспечиваемая форматом с плавающей точкой. Например, значения числа Авогадро и постоянной Планка с восемью значащими разрядами неизвестны, и было бы удобнее обозначать их соответственно через (27, +.00060221) и (-23, +.00066261), а не через (24, +.60221400) и ( — 26, +.66261000). Выло бы прекрасно, если бы можно было задавать входные данные для каждой задачй в ненормализованной форме, из которой можно было бы почерпнуть информацию об их реальной точности, и если бы в выходных данных содержалась информация о том, какова точность результата.
К несчастью, это ужасно сложная проблема, хотя использование ненормализованной арифметики н может помочь получить некоторые сведения такого рода. Например, можно говорить с большой степенью уверенности, что произведение числа Авогадро и постоянной Планка равно (1, +.00039903), а их сумма равна (27, +.00060221). (Данный пример приведен не для того, чтобы привести к мысли о том, будто сумме или произведению этих фундаментальных констант можно приписать какой-либо важный физический смысл, а чтобы продемонстрировать, что можно сохранить некоторую информацию о точности результата вычислений нэд неточными величинами, когда исходные операнды не зависят одни от другого.) Правила ненормализованной арифметики просты: пусть 1„— количество ведущих нулей в дробной части числа и = (е„, 7„), так что 1„есть наибольшее целое число < р, для которого )Я < 6 '".
Тогда сложение и вычитание выполняются точно так, как в алгоритме 4.2.1А, но все сдвиги влево, масштабирующне дробную часть, опускаются. Умножение и деление выполняются так же, как в алгоритме 4.2.1М, но результат сдвинут вправо или влево, так что его дробная часть будет начинаться в точности с шах(1„, 1„) нулей. По существу, те же правила на протяжении многих лет использовались и для традиционных вычислений вручную. Таким образом, для вычислений с ненормализованными числами имеем еи9~„евех = шах(еи еи) + (О или 1) е„в„— е„+ е„— 9 — щш(1„, 1„) — (О или 1), е з„- е„— е„+ д — 1„+ Ю„+ кпах(1„, 1„) + (О нли 1).
(48) (49) (50) Если результатом должен быть нуль, то в качестве результата вычислений выда- ется ненормализованный нуль (часто его называют величиной порядка нуль). Это означает, что в действительности результат может быть и не равен нулю, но нам просто не известен ни один его значащий разрхд! Для арифметических операций над ненормализованными числами применявшаяся ранее методика анализа ошибок принимает несколько другой вид. Введем теперь новую величину 5„= 1зЬ'" т в для п = (е„,у„). (51) Она зависит от представления числа и, а не от его значения Ь'" ту„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
