Piszę symulator fizyki w C++ i martwię się o solidność. Czytałem, że katastrofalne anulowanie może wystąpić w arytmetyzacji zmiennoprzecinkowej, gdy obliczana jest różnica dwóch liczb o niemal równej wielkości. Przyszło mi do głowy, że może się to zdarzyć w symulatorze, gdy obliczany jest iloczyn punktowy dwóch prawie ortogonalnych wektorów. Jednak odnośniki, o których wspomniałem, omawiają jedynie rozwiązanie problemu poprzez przepisanie danego równania (np. Wzór kwadratowy można przepisać w celu wyeliminowania problemu) - ale wydaje się, że nie ma to zastosowania przy obliczaniu produktu z kropką? Sądzę, że chciałbym wiedzieć, czy jest to typowy problem w silnikach fizyki i jak jest on rozwiązywany.Czy katastroficzne anulowanie jest problemem przy obliczaniu produktów kropkowych wektorów zmiennoprzecinkowych? A jeśli tak, to w jaki sposób jest on zazwyczaj rozwiązywany?
Odpowiedz
Jedną z powszechnych sztuczek jest to, aby zmienna akumulatora była typem z większą precyzją niż sam wektor.
Można również użyć Kahan summation podczas podsumowania warunków.
Innym podejściem jest użycie różnych blocked dot product algorithms zamiast algorytmu kanonicznego.
Można oczywiście połączyć oba powyższe podejścia.
Należy zauważyć, że powyższe jest ogólnym błędnym zachowaniem produktów dot, a nie konkretnie katastroficznym anulowaniem.
Dzięki za odpowiedź ... wydaje się, że rozwiązania te rozwiązują zaokrąglenia błędów, a nie anulowanie. W moim przykładzie obliczam iloczyn skalarny wektorów 2D, x1 * x2 + y1 * y2 (gdzie zmienne są zmiennoprzecinkowe). Nie sądzę, aby konwersja ich na deblu rozwiązała problem anulowania (choć może to uczynić go mniej częstym). Jeśli x1 * x2 ma prawie taką samą wartość jak y1 * y2, to nie widzę również, w jaki sposób algorytm Kahana rozwiązałby problem anulowania, który miałby miejsce ... wydaje się, że bardziej chodzi o zminimalizowanie gromadzenia się błędów w wielu sumach. –
Mówisz w komentarzu, że musisz obliczyć x1 * x2 + y1 * y2, gdzie wszystkie zmienne są zmiennoprzecinkowe. Więc jeśli wykonujesz obliczenia z podwójną precyzją, nie tracisz żadnej dokładności, ponieważ podwójna precyzja ma ponad dwa razy więcej precyzji niż zmienna (zakładając, że twój cel używa IEEE-754).
W szczególności: pozwól xx, yy być liczbami rzeczywistymi reprezentowanymi przez zmienne floatx, y. Niech xxyy będzie ich produktem, i niech xy będzie wynikiem podwójnej precyzji mnożenia x * y. Wtedy we wszystkich przypadkach xxyy jest rzeczywistą liczbą reprezentowaną przez xy.
+1: To brzmi poprawnie. Jeśli utraciłeś już precyzję przed dotarciem do produktu, nic nie możesz zrobić, aby go odzyskać. Wykonując obliczenia z podwójną precyzją, nie wprowadzasz kolejnego błędu, przynajmniej w przypadku, gdy masz tylko dwa terminy. –
Przypuszczam, że problem polega na tym, że pierwotne wartości zmiennoprzecinkowe są zaokrąglonymi przybliżeniami liczb rzeczywistych na samym początku, a więc mimo że wykonanie produktu kropkowego z podwójną precyzją nie powoduje żadnych błędów zaokrągleń (dopóki nie przekonwertujemy wartości z powrotem na wartość zmiennoprzecinkową), problem z usunięciem nadal istnieje, ponieważ produkt kropki działa na wartościach przybliżonych, od których zaczyna się (ponieważ katastroficzne anulowanie następuje, gdy błąd w tych oryginalnych wartościach staje się dominujący po odjęciu) - przekształcenie ich na podwójne nie powoduje, że oryginał wartości dokładniejsze. –
Sądzę, że użycie podwójnych globalnie pomogłoby, ponieważ pierwotne wartości byłyby wtedy dokładniejsze, ale nadal wydaje mi się, że tak długo, jak dwa wektory były wystarczająco blisko ortogonalnego, to problem nadal występował. Zasadniczo konwersja do debli na całym świecie może sprawić, że problem będzie mniej częsty, ale wydaje się, że nie omija go całkowicie. –
może coś dla [math.stackexchange] (http://math.stackexchange.com/)? –
@TomKnapen - Podczas gdy pytanie prawdopodobnie znajduje się w zakresie math.stackexchange, [faq na tej stronie] (http://math.stackexchange.com/faq) sugeruje użycie SO dla pytań dotyczących implementacji algorytmu. To pytanie należy tutaj. –
Dla wielu aplikacji nie ma znaczenia. Jeśli otrzymasz katastrofalne unieważnienie, stosunek prawidłowego produktu z kropką do obliczonego może znacznie różnić się od jednego ... ale obie wartości będą bardzo bliskie zeru, a w porównaniu do innych wartości, które obliczasz, będą nieistotne. –