TL; DR
- Użyj poniższej funkcji zamiast obecnie przyjętego rozwiązania, aby uniknąć niektórych niepożądanych wyników w pewnych przypadkach granicznych, a jednocześnie być potencjalnie bardziej wydajnym.
- Poznaj oczekiwaną niedokładność swoich liczb i odpowiednio je podawaj w funkcji porównania.
bool nearly_equal(
float a, float b,
float epsilon = 128 * FLT_EPSILON, float relth = FLT_MIN)
{
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);
}
Grafika, proszę?
Przy porównywaniu liczb zmiennoprzecinkowych istnieją dwa „tryby”.
Pierwszym z nich jest tryb względny , w którym różnica między xi yjest rozpatrywana w stosunku do ich amplitudy |x| + |y|. Przy rysowaniu w 2D daje następujący profil, gdzie kolor zielony oznacza równość xi y. (Wziąłem epsilon0,5 dla celów ilustracyjnych).
Tryb względny jest używany dla „normalnych” lub „dostatecznie dużych” wartości zmiennoprzecinkowych. (Więcej o tym później).
Drugi to tryb absolutny , kiedy po prostu porównujemy ich różnicę do ustalonej liczby. Daje następujący profil (ponownie z epsilon0,5 i relth1 dla ilustracji).
Ten absolutny tryb porównania jest używany dla „małych” wartości zmiennoprzecinkowych.
Teraz pytanie brzmi, jak połączyć te dwa wzory odpowiedzi.
W odpowiedzi Michaela Borgwardta przełącznik opiera się na wartości diff, która powinna być poniżej relth( Float.MIN_NORMALw jego odpowiedzi). Ta strefa przełączania jest pokazana jako zakreskowana na poniższym wykresie.
Ponieważ relth * epsilonjest mniejszy relth, zielone plamy nie sklejają się, co z kolei nadaje rozwiązaniu złą właściwość: możemy znaleźć trojaczki liczb takie, x < y_1 < y_2a jednak x == y2ale x != y1.
Weźmy ten uderzający przykład:
x = 4.9303807e-32
y1 = 4.930381e-32
y2 = 4.9309825e-32
Mamy x < y1 < y2i faktycznie y2 - xjest ponad 2000 razy większa niż y1 - x. A jednak przy obecnym rozwiązaniu
nearlyEqual(x, y1, 1e-4) == False
nearlyEqual(x, y2, 1e-4) == True
Z kolei w rozwiązaniu zaproponowanym powyżej strefa przełączania bazuje na wartości |x| + |y|, która jest reprezentowana przez zakreskowany kwadrat poniżej. Zapewnia, że obie strefy łączą się wdzięcznie.
Ponadto powyższy kod nie ma rozgałęzień, co mogłoby być bardziej wydajne. Weź pod uwagę, że operacje takie jak maxi abs, które a priori wymagają rozgałęzienia, często mają dedykowane instrukcje asemblacji. Z tego powodu uważam, że to podejście jest lepsze od innego rozwiązania, które polegałoby na naprawie Michaela nearlyEqualpoprzez zmianę przełącznika z diff < relthna diff < eps * relth, co spowodowałoby zasadniczo ten sam wzorzec odpowiedzi.
Gdzie przełączać się między porównaniem względnym i bezwzględnym?
Przełączanie między tymi trybami odbywa się wokół relth, co jest przyjmowane tak, jak FLT_MINw zaakceptowanej odpowiedzi. Ten wybór oznacza, że reprezentacja float32ogranicza precyzję naszych liczb zmiennoprzecinkowych.
To nie zawsze ma sens. Na przykład, jeśli porównywane liczby są wynikiem odejmowania, być może coś z zakresu FLT_EPSILONma większy sens. Jeśli są to pierwiastki kwadratowe z odejmowanych liczb, niedokładność liczbowa może być jeszcze większa.
Jest to raczej oczywiste, gdy rozważasz porównanie liczb zmiennoprzecinkowych z 0. Tutaj każde względne porównanie zakończy się niepowodzeniem, ponieważ |x - 0| / (|x| + 0) = 1. Zatem porównanie musi zostać przełączone do trybu bezwzględnego, gdy xjest na poziomie dokładności obliczeń - i rzadko jest tak niskie, jak FLT_MIN.
To jest powód wprowadzenia relthpowyższego parametru.
Ponadto, nie mnożąc relthprzez epsilon, interpretacja tego parametru jest prosta i odpowiada poziomowi dokładności numerycznej, którego oczekujemy od tych liczb.
Matematyczne dudnienie
(trzymane tutaj głównie dla własnej przyjemności)
Bardziej ogólnie zakładam, że dobrze zachowujący się operator porównania zmiennoprzecinkowego =~powinien mieć kilka podstawowych właściwości.
Oto raczej oczywiste:
- równość siebie:
a =~ a
- symetria:
a =~ bimplikujeb =~ a
- niezmienność przez opozycję:
a =~ bimplikuje-a =~ -b
(Nie mamy a =~ bi b =~ csugeruje a =~ c, że =~nie jest to relacja równoważności).
Dodałbym następujące właściwości, które są bardziej specyficzne dla porównań zmiennoprzecinkowych
- jeśli
a < b < c, to a =~ cimplikuje a =~ b(bliższe wartości również powinny być równe)
- jeśli
a, b, m >= 0to a =~ boznacza a + m =~ b + m(większe wartości z tą samą różnicą również powinny być równe)
- jeśli
0 <= λ < 1to a =~ boznacza λa =~ λb(być może mniej oczywiste do argumentowania za).
Te właściwości już dają silne ograniczenia dla możliwych funkcji bliskich równości. Weryfikuje je funkcja zaproponowana powyżej. Być może brakuje jednej lub kilku innych oczywistych właściwości.
Kiedy myślimy o =~rodzinie relacji równości =~[Ɛ,t]sparametryzowanej przez Ɛi relth, można również dodać
- jeśli
Ɛ1 < Ɛ2to a =~[Ɛ1,t] bimplikuje a =~[Ɛ2,t] b(równość dla danej tolerancji oznacza równość przy wyższej tolerancji)
- jeśli
t1 < t2to a =~[Ɛ,t1] bimplikuje a =~[Ɛ,t2] b(równość dla danej niedokładności implikuje równość przy większej nieprecyzyjności)
Zaproponowane rozwiązanie również je weryfikuje.