в свете возможного невыполнения закона ассоциативности приведенное в начале этой главы замечание госпожи Л а Туш (La Touche), если его отнести к арифметике в формате с плавающей точкой, несет в себе большую долю здравого смысла. Математические обозначения наподобие "01-1-02+03" и "Ylk=i к" по самому своему существу основаны на предположении об ассоциативности, так что программист должен быть особенно бдителен на сей счет, задаваясь постоянно вопросом, не предполагается ли неявно справедливость закона ассоциативности.

А. Аксиоматический подход. Хотя закон ассоциативности и не выполняется, закон коммутативности

uev - v®u (2)

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

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

uev = u®-v; (3)

-{u®v) = -u®-v; (4)

ы ф v = О тогда и только тогда, когда v = -и; (5)

и®0 = и. (6)

Из этих законов можно получить и другие тождества, например (см. упр. 1)

uev = -(vQu). (7)

Тождества (2)-(6) легко выводятся из алгоритмов, описанных в разделе 4.2.1. Следующее правило менее очевидно:

если и <v, то ифъи <v®w. (8)

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

ы ф г> = round(M + г>), и Q v = Tound{u - v),

ы 0 v = round(M X v), u0v = round(M / v),

где round(a:) означает наиболее близкое приближение в фор.мате с плавающей точкой к X, как определено в алгоритме 4.2.IN. Имеем

round(-i) = -round(i), (10)

X <у влечет round(ar) < round(j/). (И)

Из этих фундаментальных соотношений свойства (2)-(8) следуют немедленно. Теперь можно вьшисать еще несколько тождеств, вытекающих из указанных выше соотношений:

ы (gi г; = v ® «, (-ы) 0 г> = -(« 0 г>), 1 ® v = v; и0у = О тогда и только тогда, когда ы = О или v = 0; {-и) (Z>v = u0 {-v) = -{и 0 v); 00V = 0, и 01 = и, u0u = l.

Если u<viiw>0, vou0w<v0wHu0w<v0w; также w 0 и > w 0 v, если г> > « > 0. Если и ® v = и + v, то (и ф v) Q v = и; если u0v = uxvO, то {и 0 v) 0 V = и. Как видно, несмотря на природную "неточность" операций в формате с плавающей точкой, им присуща значительная регулярность, если все как следует продумать.

Все же в приведенном выше наборе тождеств, разумеется, бросается в глаза отсутствие нескольких известных законов алгебры; закон ассоциативности для умножения в формате с плавающей точкой выполняется не вполне точно, как будет видно из упр. 3. Что же касается закона дистрибутивности, связывающего операции 0 и ©, то он может нарушаться, и при этом довольно значительно. Пусть, например, и = 20000.000, V = -6.0000000 и ш = 6.0000003; тогда

(м 0 и) © (« 0 ш) = -120000.00 © 120000.01 = .010000000

u0{v®w) = 20000.000 0 .00000030000000 = .0060000000.

Таким образом,

u0{v®w) {u0v)®{u0w). (12)

С другой стороны, действительно справедливо 6 0 (и © ш) = {b0v) ® {b0w), когда b есть основание системы счисления, поскольку

round(6i) = 6round(a:). (13)

(Строго говоря, в тождествах и неравенствах, которые рассматриваются в этом разделе, неявно подразумевается, что потеря значимости или переполнение порядка не возникает. Функция округления round(i) не определена, когда i слишком мало или слишком велико, и равенства, подобные (13), имеют место только в случае, когда обе части определены.)

Другой впечатляющий пример нарушения законов традиционной алгебры при работе с числами в формате с плавающей точкой - невыполнение фундаментального неравенства Коши

{х1 + ---+ х1){у1 +---+у1)> (хгуг ++ ХпУп?

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

сг =

«) )/»(»-!) М

V l<fc<n Vl<fc<n /

ц часто при выполнении программы "нарываются" на попытку извлечения квадратного корня из отрицательного числа! Значительно лучший метод вычисления среднего значения и стандартного отклонения с учетом свойств операций в формате с плавающей точкой состоит в использовании рекуррентных формул

Ml = хи Mk = Мк-1 Ф {xk е Mk-i) 0 к, (15)

Si = o, Sk = Sk-i Ф {хк е Mk-i) ® {хк е Мк) (16)

для 2 < А; < п, где а = у/ЗпЦп - 1). [См. В. Р. Welford, Technometrics 4 (1962), 419-420.] При использовании этого метода 5„ никогда не может быть отрицательным и можно избежать множества других серьезных проблем, возникающих при слишком доверчивом отношении к накоплению сумм, как показано в упр. 16. (О методах суммирования, обеспечивающих даже более высокую гарантированную точность, речь идет также в упр. 19.)

Даже если алгебраические законы выполняются не вполне строго, можно использовать описанные методы для определения того, насколько точно выполняется тот или иной закон. Когда Ь~ < х < Ь, имеем round(i) = х + р{х), где \р{х)\ < Ь". Следовательно,

round(i) =i(l-b(5(i)), (17)

где относительная ошибка ограничена независимо от х:

Шх)\ = 1 < 1()1 < " < Ч-Р (18)

Это неравенство можно использовать в качестве простого инструмента для оценки относительной погрешности вычислений, выполняемых с нормализованными числами в формате с плавающей точкой, поскольку и ® v = {и + v) {l + S{u + v)) и т. д.

В качестве примера типичной процедуры оценки ошибки рассмотрим закон ассоциативности умножения. Как показано в упр. 3, (ы 0 г>) 0 w, вообще говоря, не равно ы 0 (и 0 и;), но ситуация в данном случае намного лучше, чем в случае применения закона ассоциативности сложения (1) и закона дистрибутивности (12). На самом деле, имеем

(m0v) 0и; = ((uv)(l +Si)) 0w = uvw{l +Si){l +S2), Ы 0 (v 0 и;) = Ы 0 {{vw){l +S3)) = uvw{l + 6з){1 +64)

для некоторых Si, 62,63, 64 при условии, что не происходит переполнения или исчезновения порядка, причем \6j\ < Ь~ для каждого j. Следовательно,

(м 0 г)) 0 w (1 -Ь 6i){l + 62)

<5 <2б1-Р/(1-i6l-P) (19)

В анализе точности очень часто появляется число Ь~, которому дано специальное наименование - один ulp, что означает одну единицу в последнем разряде дробной части (Unit in the Last Place). Операции с числами в формате с плавающей точкой дают результат с точностью до половины ulp, и вычисление uvw посредством двух умножений в формате с плавающей точкой имеет точность около одного ulp