Тест на переполнение
Предположим:
- В реализации C используется арифметика IEEE-754 с округлением до ближайшего числа, связанного с четным.
- Величина делителя не более 1, а делитель ненулевой.
- Делитель положительный.
Тест и приведенное ниже доказательство написаны с помощью приведенного вышепредположения для простоты, но общие случаи легко обрабатываются:
- Если делитель может быть отрицательным, используйте
fabs(divisor) вместо divisor при расчете limit, показанном ниже. - Если делитель равен нулю, нет необходимости проверять переполнение, поскольку уже известно, что возникает ошибка (деление на ноль).
- Если величина превышает 1, деление никогда не создаетсяновый переполнение.Переполнение происходит только в том случае, если дивиденд уже равен бесконечности (поэтому проверка будет
isinf(candidate)).(При делителе, превышающем 1 по величине, деление может быть недостаточным. В этом ответе не обсуждается тестирование на предмет недостаточного значения в этом случае.)
Примечание к записи: выражения, использующие операторы не в формате кода, напримеркак x • y, представляют точные математические выражения без округления с плавающей точкой.Выражения в формате кода, такие как x*y, означают вычисленные результаты с округлением с плавающей запятой.
Чтобы обнаружить переполнение при делении на divisor, мы можем использовать:
FL_64 limit = DBL_MAX * divisor;
if (-limit <= candidate && candidate <= limit)
// Overflow will not occur.
else
// Overflow will occur or candidate or divisor is NaN.
Доказательство:
limit будет равно DBL_MAX, умноженному на divisor и округленному до ближайшего представимого значения.Это точно DBL_MAX • divisor • (1 + e ) для некоторой ошибки e , такой, что -2 −53 ≤ e ≤ 2 −53 , благодаря свойствам округления до ближайшего плюс тот факт, что никакое представимое значение для divisor не может при умножении на DBL_MAX привести к значению ниже нормального диапазона.(В субнормальном диапазоне относительная погрешность из-за округления может быть больше, чем 2 -53 . Поскольку продукт остается в нормальном диапазоне, этого не происходит.)
Однако e = 2 -53 может произойти только в том случае, если точное математическое значение DBL_MAX • divisor находится точно посередине между двумя представимыми значениями, что требует наличия 54 значащих бит (бит, равный ½ самой низкой позиции 53-битного значимого числа представимых значений, равен 54 th , считая от начального бита).Мы знаем, что значение DBL_MAX равно 1fffffffffffff 16 (53 бита).Умножение на нечетные числа дает 1fffffffffffff 16 (при умножении на 1), 5ffffffffffffd 16 (на 3) и 0x9ffffffffffffb 16 (на 5) и числас более значимыми битами при умножении на большие нечетные числа.Обратите внимание, что 5ffffffffffffd 16 имеет 55 значащих бит.Ни один из них не имеет ровно 54 значащих бита.При умножении на четные числа произведение имеет конечные нули, поэтому число значащих битов такое же, как и при умножении на нечетное число, которое получается в результате деления четного числа на наибольшую степень двух, которая его делит.Следовательно, ни одно произведение DBL_MAX не находится точно посередине между двумя представленными значениями, поэтому ошибка e никогда не бывает точно 2 -53 .Итак −2 53 <<em> e <2 <sup>-53 .
Итак, limit = DBL_MAX • divisor • (1 + e ), где e <2 <sup>-53 .Следовательно, limit / divisor равно DBL_MAX • (1 + e ).Поскольку этот результат меньше ½ ULP от DBL_MAX, он никогда не округляется до бесконечности, поэтому он никогда не переполняется.Таким образом, деление любого candidate, которое меньше или равно limit на divisor, не переполняется.
Теперь мы рассмотрим кандидатовпревышающий limit.Как и в случае с верхней границей, e не может быть равен -2 -53 по той же причине.Тогда наименьшее значение e может быть равно -2 −53 + 2 −105 , поскольку произведение DBL_MAX и divisor имеет не более 106 значимыхбиты, поэтому любое увеличение от средней точки между двумя представленными значениями должно быть как минимум на одну часть в 2 -105 .Затем, если limit < candidate, candidate хотя бы на одну часть в 2 -52 больше limit, поскольку в значении есть 53 бита.Итак DBL_MAX • divisor • (1−2 −53 + 2 −105 ) • (1 + 2 −52 ) <<code>candidate,Тогда candidate / divisor не менее DBL_MAX • (1−2 −53 + 2 −105 ) • (1 + 2 −52 ), что составляет DBL_MAX • (1 + 2 −53 + 2 −157 ).Превышение средней точки между DBL_MAX и тем, что будет следующим представимым значением, если диапазон экспоненты не ограничен, что является основой для критерия округления IEEE-754.Следовательно, он округляется до бесконечности, поэтому возникает переполнение.
Недостаточное значение
При делении на число, величина которого меньше единицы, число, конечно, увеличивается по величине, поэтому оно никогда не уменьшается до нуля.Тем не менее, определение недостаточного значения в IEEE-754 состоит в том, что ненулевой результат является крошечным (в субнормальном диапазоне), либо до, либо после округления (использование до или после определяется реализацией).Конечно, возможно, что деление субнормального числа на divisor меньше единицы приведет к результату, все еще находящемуся в субнормальном диапазоне.Однако, чтобы это произошло, недопущение должно было произойти ранее, чтобы получить субнормальные дивиденды в первую очередь.Таким образом, недопущение никогда не будет введено делением на число с величиной меньше единицы.
Если кто-то хочет проверить это недопущение, можно сделать аналогично проверке переполнения, сравнив кандидата сминимальное нормальное (или наибольшее субнормальное), умноженное на divisor - но я еще не работал с числовыми свойствами.