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

Таким образом, показано, что {и0и)0т приблизительно равно и0{у0ю), за исключением тех случаев, когда происходит исчезновение или переполнение порядка. Эта интуитивная идея "приблизительного равенства" заслуживает более подробного изучения; можно ли дать более точную формулировку этого утверждения?

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

о котором известно из литературы, что i„ стремится к некоторому пределу при п 00, то, скорее всего, будет ошибкой продолжать вычисления, пока для некоторого п не выполнится равенство Xn+i = з:„, так как последовательность аг„ может ввиду округления промежуточных результатов оказаться периодической с большим периодом. Разумно продолжать вычисления лишь до тех пор, пока для некоторого подходящим образом выбранного S не станет справедливым неравенство in+i - х„ < (5; но так как порядок величины i„ заранее неизвестен, еще лучше - дождаться выполнения неравенства

\Хп+1 - Хп\ < €\Хп\, (20)

где е - число, которое должно быть выбрано заранее. Соотношение (20) позволяет другим способом выразить то, что числа Xn+i и i„ приблизительно равны; и наше обсуждение показывает, что при анализе вычислений над числами с плавающей точкой отношение "приблизительного равенства" было бы более полезно, чем традиционное отношение равенства, если только первое отношение удастся определить надлежащим образом.

Другими словами, тот факт, что строгое равенство величин в формате с плавающей точкой играет очень небольшую роль, приводит к необходимости ввода новой операции сравнения величин с плавающей точкой, назначение которой - упростить оценку относительных значений двух таких величин. Представляются подходящими следующие определения для чисел с плавающей точкой и = (€„,/„) и v = (е„, /ц) по основанию b с избытком q:

u<v (е) тогда и только тогда, когда v - и> €mяx{b~ ,Ь~); (21)

ы ~ v (е) тогда и только тогда, когда \и -и\< етах(Ь"~,Ь"~); (22)

иУи (е) тогда и только тогда, когда ы - v > етах(Ь"~,Ь~); (23)

ufvv (е) тогда и только тогда, когда u - ы < е min(b"~, Ь""). (24)

Эти определения подходят как для нормализованных чисел, так и для ненормализованных. Согласно этим определениям для любой данной пары значений ими может выполняться в точности одно из соотношений к и (определенно меньше), и ~ V (приблизительно равно) или и у v (определенно больше). Отношение и т v несколько более сильное, чем ы ~ v, и его можно читать так: "ы, по существу.

и то же самое неравенство выполняется, если поменять местами (и 0 у;) 0 ш и {v<S>w). Следовательно, в соответствии с (34) справедливо соотношение

{и (Si V) (Si W к и ® (v (Si W) (б) (39)

для б > 2бо/(1 - бо)- Например, при 6 = 10 и р = 8 можно взять е = 0.00000021.

Соотношения Ч, ~, и « полезны для численных алгоритмов, и поэтому разумно включить в состав системного программного обеспечения компьютера программы для сравнения чисел с плавающей точкой наряду с программами для выполнения над ними арифметических действий.

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

Теорема А. Пусть и и v -нормализованные числа с плавающей точкой. Тогда

{{и®v)eu) + {{и@v)e {{u®v)eu)) =u®v (40)

при условии, что не происходит переполнения или исчезновения порядка.

Это довольно громоздкое тождество можно переписать в следующем более простом виде. Положим

и = {u®v)Ov , v = {u®v)Qu;

(41)

u" = {u®v)ev, v" = {u@v)eu.

Интуитивно ясно, что и и и" должны быть приближениями к u, а у; и v" - приближениями к V. Теорема А утверждает, что

u@v = и + v" =и" + Ь. (42)

Это более сильное утверждение, нежели тождество

u@v = u @v" =и" @v, (43)

являющееся следствием округления (42).

Доказательство. Будем говорить, что t является остаточным членом х (по модулю Ь), если

t = x (по модулю 6"), \t\ < i6 (44)

Таким образом, x~round(x) всегда равно остаточному члену х. Доказательство теоремы А в значительной мере основывается на следующих простых умозаключениях, доказанных в упр. 11.

Лемма Т. Если t есть остаточный член числа в формате с плавающей точкой х, то xQt = X - t. I

Пусть w = u®v. Теорема A становится тривиальной, когда w = 0. Умножив все переменные на подходящие степени Ь, можно, не теряя общности, предположить, что Cyj = р. Тогда и + V = W + г, где г есть остаточный член u + v (по модулю 1). Далее, и = round(u; -v) = round(u - г) =u-r -t, где t есть остаточный член и-г (по модулю 6) и е = €„ -р-

Если е < О, то i = u - г = -у; (по модулю 6). Следовательно, t есть остаточный член -V и v" = round(u; - и) = round(j; + t) = v + t, что доказывает (40). Если е > О, то \и-г\ > а поскольку г < , имеем и >6р-1. Из этого следует, что u есть

целое число, так что г - остаточный член v (по модулю 1). Если и = и, то t = -г является остаточным членом -v. В противном случае соотношение round(u-r) ф и влечет за собой и = 6-1, г = , = Ь, t = г; опять же, t - остаточный член -v. I

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

Теорема В. В предположениях теоремы А и при условии (41) справедливо тождество

u-\-v = {u@v)-\-{{иеи) @ {v ev")). (45)

Доказательство. Рассматривая каждый из случаев, возникших при доказательстве теоремы А, мы неизменно обнаруживаем, что и Q и = и - и, v Q v" = v - v" и (u - и) ® [v - v") = (u - u) + [v - v"). Значит, (45) следует из теоремы А. Если учесть принятые в предыдущем доказательстве обозначения, эти соотношения окажутся эквивалентными следующим:

round(i + г) = f + г, round(i) = t, round(r) = г. (46)

В упр. 12 рассматривается теорема для особого случая, когда \еи - е„ > р. Иначе u-\-v имеет не более 2р значащих разрядов, и можно легко показать, что round(r) = г. Если теперь е > О, доказательство теоремы А показывает, что f = -г или i = г = ±\. Если е < О, имеем t + г = и и t = -v {по модулю ¥); этого достаточно для доказательства того, что t + г и t при округлении не изменяются (округляются до "самих себя"), обеспечивая выполнение неравенств вц > е и е„ > е. Но либо Си < О, либо е„ < О будут противоречить нашей гипотезе о том, что еи - < р, поскольку е,„ = р.

Теорема В дает в явном виде формулу для получения разности между u-\-v и u@v в терминах величин, которые можно вычислить, непосредственно используя пять арифметических операций в формате с плавающей точкой. Если основание системы счисления Ь равно 2 или 3, можно улучшить этот результат и получить точные значения корректирующих членов, используя всего две арифметические операции в формате с плавающей точкой и одно сравнение абсолютных величин в формате с фиксированной точкой.

Теорема С. Если 6 < 3 и и > 7;, то

u-\-v = {u®v)-¥ {uQ{u®v)) ®v. (47)

Доказательство. Следуя соглашениям, принятым при доказательстве предьщущих теорем, желательно показать, что vQv = г. Достаточно показать, что v = w - и, поскольку из (46) затем последует v Q у = round(7; - v) - round(u -\- v - w) = round(r) = r.

Фактически нужно доказать (47) для любых 6 < 3 и вц > е,,. Если вц > р, то г есть остаточный член v (по модулю 1). Значит, v = wQu = vQr = v - r = w - и,