Некоторые предварительные условия:
Я предполагаю, что используется арифметика IEEE-754 с двоичным основанием и округлением до ближайших связей к четности.
Далее я предполагаю, что все операнды и результаты операций конечны (ни бесконечности, ни NaN). (Если возможны бесконечности или NaN, утверждение неверно. Если величины a и b немного меньше наибольшего представимого конечного значения, но имеют противоположные знаки, то a−b - это бесконечность, поэтому a−b+b−a - это бесконечность, и ее величина превышает ULP, равную a .)
Курсив обозначает математические переменные, такие как a и b . Формат кода обозначает вычисленную арифметику, такую как a+b, тогда как a + b является точным математическим результатом.
Я предполагаю, что a и b представимы, то есть мы начинаем с a , равного a и b равно b, не начинается с произвольных действительных чисел a и b , которые сначала преобразуются в представимые значения a и b.
Наибольшая ошибка в округлении до ближайших связей к четному составляет 1/2 ULP математического результата. Это верно, потому что любой результат лежит на представимом значении или между двумя представимыми значениями. Если оно находится между двумя значениями, округление до ближайшего выбирает более близкое, расстояние до которого составляет не более половины расстояния между ними.
Для «ULP x » я напишу ULP ( x ). Если x не является представимым значением, ULP ( x ) является ULP с наибольшим представимым значением, меньшим чем | x |.
| а - б | не более 2 | a |, поскольку | b | ≤ | a |. Таким образом, ошибка в a−b составляет максимум ½ ULP (2 | a |), что составляет 1 ULP ( a ). Таким образом, a−b = a - b + e для некоторой ошибки округления e с | e | ≤ ULP ( a ).
Теперь рассмотрим математический результат сложения a−b и b. Математический результат: a−b + b = a - b + e + b = а + е . Таким образом, математический результат находится в пределах 1 ULP a включительно. К чему тогда это может округлить?
По определению ULP следующее представимое число, большее по величине, чем a , равно a + ULP ( a ). 1 Следующее представимое число, меньшее по величине, чаще всего является a - ULP ( a ), но может быть a - ½ ULP ( a * 1138) *) если a - это ровно степень двух (так что это наименьшее число в бинаде, а следующее нижнее число имеет меньший показатель степени). Даже в этом случае есть и другое представимое число в a - ULP ( a ).
Таким образом, математикареальный результат, a + e , лежит в закрытом интервале [ a −ULP ( a ), a + ULP ( a )], который ограничен двумя представимыми числами. Пусть x будет той конечной точкой, которая ближе к a + e , и предположим, что a + e округляется до y в соответствии с правилом округления до ближайших связей к четным. Если y находится вне интервала, то расстояние от a + e до y больше, чем расстояние до x , либо потому, что y находится за x в том же направлении, либо потому, что y лежит в другом направлении и, следовательно, находится за пределами другой конечной точки, которая по крайней мере, так далеко от a + e , как x , так что y дальше. Следовательно, a + e округляется до одной из конечных точек или до некоторого другого представимого числа внутри интервала. Таким образом, оно округляется до некоторого числа в пределах одного ULP, равного a включительно.
Таким образом, a−b+b - самое большее 1 ULP ( a ) от a .
Сноска
1 В целях округления, если x является наибольшим представимым конечным значением, обрабатывается x + ULP ( x ) в качестве представителя до тех пор, пока не будет принято решение о округлении. Если в результате округления будет выбран x + ULP ( x ), результат будет ∞. (И то же самое верно для симметрично для отрицательных значений.)