AOP_Tom2 (1021737), страница 74
Текст из файла (страница 74)
Наименее значимый разряд в дробной части числа в формате с плавающей точкой часто образуется в результате округлении остатка при последовательно выполняемых операциях, и это правило позволяет, насколько это возможно, избежать формирования значения Ь/2 в наименее значимом разряде. На практике применение этого правила приводит к тому, что выделяется некоторая память для подозрительных операций округления, чтобы последовательные округления имели тенденцию к формированию результата, не вызывающего неоднозначного толкования. Например, если округлять до нечетного в десятичной системе, повторяющиеся операции округления числа 2.44445 с "укорачиваиием" на один разряд дадут результат в виде последовательности 2.4445, 2.445, 2.45, 2.5, 3; если же округлять до четного, подобные ситуации не возникнут, хотя повторяющееся округление чисел наподобие 2.5454 приведет к почти такой же ошибке.
[См. Ноу А. Ке)г, 1пб Ргос. Ъемегв 3 (1975), 188-189.] Иногда предпочтение отдается округлению до четного в любом случае, и в результате наименее значимый разряд оказывается равным 0 чаще. В у~р. 23 продемонстрировано это преимущество округления до четного. Но, в конце концов, ни один из альтернативных вариантов не имеет решающего преимущества над другими. К счастью, обычно в качестве основания системы счисления используется Ь = 2 или Ь = 10, и тогда все согласны, что правило округления до четного является наилучшим.
Читатель, который заинтересуется деталями доказательства изложенных выше положений, обнаружит существенное упрощение задачи, которое предоставляет простое правило и Ю п = гоппс)(и+ и). Если бы подпрограмма сложения в формате с плавающей точкой не следовала этому правилу в любом, даже в самом редком, случае, доказательство стало бы существенно более сложным и, возможно, его вообще не удалось бы сформулировать. Теорема В не выполняется, если вместо округления используется арифметическое "усечение", т. е. если положить и сэ е = 1гипс(и+ и) и и я е = Ггппс(и — с), где 1гппс(х) для действительных положительных х есть наибольшее чи<шо в формате с плавающей точкой, которое < х.
Исключение из теоремы В возникло бы, следовательно, в случаях, подобных (20, +.10000001) а (10, —.10000001) = (20, +.10000000), когда разность между и + е и и б ь не может быть точно выражена в виде числа в формате с плавающей точкой. Также исключением был бы случай, подобный 12345678 9 .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„— количество ведущих нулей в дробной части числа и = (е„, у„), так что 1„есть наибольшее целое число < р, для которого )/„~ < Ь ц.
Тогда сложение и вычитание выполняются точно так, как в алгоритме 4.2.1А, но все сдвиги влево, масштабирующие дробную часть, опускаются. Умножение и деление выполняются так же, как в алгоритме 4.2.1М, но результат сдвинут вправо или влево, так что его дробная часть будет начинаться в точности с п1ах(1„,1„) нулей. По существу, те же правила на протяжении многих лет использовались и для традиционных вычислений вручную.
Таким образом, для вычислений с ненормализованными числами имеем аиду, еиою = шах(еи, еь) + (О илн 1), е и„— — е„+е„— д — пнп(1„,1„) — (О или 1), е„р, — — е„— е„+ д — 1„+1„+ шах(1„,1„) + (О или 1). (48) (49) (50) Если результатом должен быть нуль, то в качестве результата вычигчений выдается ненормализованный нуль (чвсто его называют величиной порядка нуль).
Это означает, что в действительности результат может быть и не равен нулю, но нам просто не известен ни один его значащий разряд! Для арифметических операций над ненормализованными числами применявшаяся ранее методика анализа ошибок принимает несколько другой внд. Введем теперь новую величину ди — 16х" т г для и = (е„,~„). (51) Она зависит от представления числа и, а не от его значения 5'" ~,(„. Правило округления гласит: )и8е — (и+в)( <Б„в„, ~и8е — (и — и)) <б и (пЗп — (и хи)( < д„в„, (иОп — (и / е)( < бье~.
Этн неравенства применимы как к нормализованным, так н к ненормализованным величинам; основное различие между двумя типами анализа ошибок состоит в том, что порядок результата каждой из операций (соотношения (48)-(50)) определяется по-другому. Отношения <,,;- и в, определенные выше в настоящем разделе, сохраняют смысл и для ненормализованных чисел. В качестве примера использования этих отношений докажем приближенный закон ассоциативности для сложения ненормализованных величин по аналогии с (39): (и8е)8ю и8(в8ю) (г) (52) для подходящим образом выбранного с. Имеем !(и 8 и) 8 ш — (и + п + ш) / < /(и 8 и) 8 ю — ((и 8 е) + ю) ) + /и 8 е — (и + и) / < 4(иве)вы+ А,|с < 2б(ищи)вы.
Аналогичная формула справедлива и для /и 8 (е 8 ю) — (и + е + ш)!. Но поскольку е<„в„),ь,„— — шах(е„, е„, е„) + (О, 1 нли 2), то 6<„п„>в„, < Ьзд„~1„~„,~. Следовательно, (52) верно при е ) бэ г + 5 г. С точки зрения закона ассоциативности сложение ненормализованных величин не вызывает столько ошибок, как сложение нормализованных. Следует подчеркнуть, что арифметика ненормализованных величин ни в коей мере нс может служить панацеей; иногда указываемая при таком способе выполнения вычислений точность больше действительной (например, сложение большого числа малых приблизительно одинаковых по абсолютной величине чисел или нахождение х" для большого и). Существует еще больше примеров, когда в такой арифметике дается невысокая точность, в то время как при выполнении операций над нормализованными величинами в действительности получались бы гораздо более точные результаты.
Существует важная причина, по которой ни один прямой метод анализа ошибок "по одной операции" не может считаться удовлетворительным, а именно.' операнды обычно не являются независимыми, Это означает, что ошибки имеют тенденцию к компенсации или усилению одна другой необычным образом. Предположим, например, что х приблизительно равно 1/2 и что у этого значения есть приближение у = х+б с абсолютной ошибкой б. Чтобы вычислить произведение х(1 — х)., можно найти у(1 — у); если х = — + е, то получим у(1 — у) = х(1 — х)— э г 2еб- б .
Таким образом, абсолютная ошибка существенно уменьшилась — перед ней появился коэффициент 2е+ 4! Это всего лишь один из случаев, когда умножение приближенных значений операндов, не являющихся независимыми, может привегти к довольно точному результату. Более очевидный пример — вычисление х 9 х, которое может быть выполнено с абсолютной точностью независимо от того, насколько ошибочным было приближение х, которое используется в качестве операнда.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
