TL; DR
- Используйте следующую функцию вместо принятого в настоящее время решения, чтобы избежать некоторых нежелательных результатов в определенных предельных случаях, будучи потенциально более эффективным.
- Знайте ожидаемую неточность ваших чисел и введите их соответствующим образом в функции сравнения.
bool nearly_equal(
float a, float b,
float epsilon = 128 * FLT_EPSILON, float relth = FLT_MIN)
// those defaults are arbitrary and could be removed
{
assert(std::numeric_limits<float>::epsilon() <= epsilon);
assert(epsilon < 1.f);
if (a == b) return true;
auto diff = std::abs(a-b);
auto norm = std::min((std::abs(a) + std::abs(b)), std::numeric_limits<float>::max());
return diff < std::max(relth, epsilon * norm);
}
Графика, пожалуйста?
При сравнении чисел с плавающей запятой существует два "режима".
Первым является режим относительно , где разница между x и y считается относительно их амплитуды |x| + |y|. При построении в 2D, это дает следующий профиль, где зеленый означает равенство x и y. (Я взял epsilon 0,5 для иллюстрации).
Относительный режим - это то, что используется для «нормальных» или «достаточно больших» значений с плавающей запятой. (Подробнее об этом позже).
Второй режим - абсолютный , когда мы просто сравниваем их разницу с фиксированным числом. Это дает следующий профиль (снова с epsilon 0,5 и relth 1 для иллюстрации).
Этот абсолютный режим сравнения используется для «крошечных» значений с плавающей запятой.
Теперь вопрос в том, как мы можем соединить эти два шаблона ответа.
В ответе Майкла Боргвардта, переключатель основан на значении diff, которое должно быть ниже relth (Float.MIN_NORMAL в его ответе). Эта зона переключения показана заштрихованной на графике ниже.
Поскольку relth * epsilon меньше, чем relth, зеленые пятна не слипаются, что, в свою очередь, придает решению плохое свойство: мы можем найти тройки чисел, такие что x < y_1 < y_2 и все же x == y2, но x != y1.
Возьмите этот яркий пример:
x = 4.9303807e-32
y1 = 4.930381e-32
y2 = 4.9309825e-32
У нас есть x < y1 < y2, и на самом деле y2 - x более чем в 2000 раз больше, чем y1 - x. И все же с текущим решением,
nearlyEqual(x, y1, 1e-4) == False
nearlyEqual(x, y2, 1e-4) == True
Напротив, в предложенном выше решении зона переключения основана на значении |x| + |y|, которое представлено заштрихованным квадратом ниже. Это гарантирует, что обе зоны соединяются изящно.
Кроме того, приведенный выше код не имеет ветвления, что может быть более эффективным. Учтите, что такие операции, как max и abs, которые a priori требуют ветвления, часто имеют специальные инструкции по сборке. По этой причине, я думаю, что этот подход превосходит другое решение, которое будет заключаться в исправлении nearlyEqual Майкла путем изменения переключателя с diff < relth на diff < eps * relth, который затем будет производить по существу тот же шаблон ответа.
Где переключаться между относительным и абсолютным сравнением?
Переключение между этими режимами производится около relth, что в принятом ответе принимается за FLT_MIN. Этот выбор означает, что представление float32 - это то, что ограничивает точность наших чисел с плавающей запятой.
Это не всегда имеет смысл. Например, если сравниваемые вами числа являются результатом вычитания, возможно, что-то в диапазоне FLT_EPSILON имеет больше смысла. Если они представляют собой квадратные корни из вычитаемых чисел, численная неточность может быть даже выше.
Это довольно очевидно, если рассмотреть сравнение с плавающей запятой с 0. Здесь любое относительное сравнение не удастся, потому что |x - 0| / (|x| + 0) = 1. Таким образом, для сравнения необходимо переключиться в абсолютный режим, когда x имеет порядок неточности в ваших вычислениях - и редко бывает настолько низким, как FLT_MIN.
Это причина для введения параметра relth выше.
Кроме того, не умножая relth на epsilon, интерпретация этого параметра проста и соответствует уровню числовой точности, который мы ожидаем от этих чисел.
Математическое урчание
(хранится здесь в основном для собственного удовольствия)
В более общем смысле я предполагаю, что у хорошо себя работающего оператора сравнения с плавающей запятой =~ должны быть некоторые основные свойства.
Следующее довольно очевидно:
- self-равенства:
a =~ a - симметрия:
a =~ b подразумевает b =~ a - неизменность оппозиции:
a =~ b подразумевает -a =~ -b
(У нас нетa =~ b и b =~ c подразумевают a =~ c, =~ не является отношением эквивалентности).
Я бы добавил следующие свойства, которые более специфичны для сравнений с плавающей запятой
- если
a < b < c, то a =~ c подразумевает a =~ b (более близкие значения также должны быть равными) - , если
a, b, m >= 0, тогда a =~ b подразумевает a + m =~ b + m (большие значения с той же разницей также должны бытьравно) - если
0 <= λ < 1, то a =~ b подразумевает λa =~ λb (возможно, менее очевидный аргумент для).
Эти свойства уже дают строгие ограничения на возможные функции, близкие к равенству,Предложенная выше функция проверяет их.Возможно, отсутствуют одно или несколько очевидных в других отношениях свойств.
Когда кто-то думает о =~ как о семействе отношений равенства =~[Ɛ,t], параметризованном Ɛ и relth, можно также добавить
- если
Ɛ1 < Ɛ2, то a =~[Ɛ1,t] b подразумевает a =~[Ɛ2,t] b (равенство для данного допуска подразумевает равенство при более высоком допуске) - , если
t1 < t2, то a =~[Ɛ,t1] b подразумевает a =~[Ɛ,t2] b (равенстводля данной неточности подразумевается равенство при более высокой неточности)
Предлагаемое решение также проверяет их.