Czy matematyka zmiennoprzecinkowa jest spójna w C #? Może być?

Nie, to nie jest kolejne pytanie „Dlaczego jest (1 / 3.0) * 3! = 1” .

Ostatnio dużo czytałem o zmiennoprzecinkowych; a konkretnie, w jaki sposób te same obliczenia mogą dać różne wyniki w przypadku różnych architektur lub ustawień optymalizacji.

Jest to problem z grami wideo, które przechowują powtórki lub są w sieci peer-to-peer (w przeciwieństwie do serwera-klienta), które polegają na tym, że wszyscy klienci generują dokładnie te same wyniki za każdym razem, gdy uruchamiają program - mała rozbieżność w jednym obliczenia zmiennoprzecinkowe mogą prowadzić do drastycznie odmiennego stanu gry na różnych maszynach (lub nawet na tej samej maszynie! )

Dzieje się tak nawet w przypadku procesorów „zgodnych” z IEEE-754 , głównie dlatego, że niektóre procesory (mianowicie x86) używają podwójnej rozszerzonej precyzji . Oznacza to, że używają 80-bitowych rejestrów do wykonywania wszystkich obliczeń, a następnie skracają je do 64- lub 32-bitowych, co prowadzi do innych wyników zaokrągleń niż maszyny, które używają 64- lub 32-bitów do obliczeń.

Widziałem kilka rozwiązań tego problemu online, ale wszystkie dla C ++, a nie C #:

• Wyłącz tryb podwójnej rozszerzonej precyzji (aby wszystkie doubleobliczenia korzystały z 64-bitowego IEEE-754) przy użyciu _controlfp_s(Windows), _FPU_SETCW(Linux?) Lub fpsetprec(BSD).
• Zawsze uruchamiaj ten sam kompilator z tymi samymi ustawieniami optymalizacji i wymagaj, aby wszyscy użytkownicy mieli tę samą architekturę procesora (bez odtwarzania na różnych platformach). Ponieważ moim „kompilatorem” jest w rzeczywistości JIT, który może optymalizować inaczej za każdym razem, gdy program jest uruchamiany , nie sądzę, aby było to możliwe.
• Używaj arytmetyki stałoprzecinkowej, unikaj floati doublecałkowicie. decimaldziałałby w tym celu, ale byłby znacznie wolniejszy i żadna z System.Mathfunkcji biblioteki go nie obsługuje.

Czy to w ogóle problem w C #? Co jeśli zamierzam obsługiwać tylko system Windows (nie Mono)?

Jeśli tak, czy istnieje sposób, aby zmusić mój program do działania z normalną podwójną precyzją?

Jeśli nie, czy są jakieś biblioteki, które pomogłyby zachować spójność obliczeń zmiennoprzecinkowych?

Nie znam sposobu, aby uczynić normalne zmiennoprzecinkowe deterministyczne w .net. JITter może tworzyć kod, który zachowuje się inaczej na różnych platformach (lub między różnymi wersjami .net). Zatem użycie normalnych floatsw deterministycznym kodzie .net nie jest możliwe.

Rozwiązania, które rozważałem:

1. Zaimplementuj FixedPoint32 w C #. Chociaż nie jest to zbyt trudne (mam już niedokończoną implementację), bardzo mały zakres wartości sprawia, że ​​jest to denerwujące w użyciu. Musisz cały czas uważać, aby nie przepełnić ani nie stracić zbyt dużej precyzji. W końcu nie było to łatwiejsze niż bezpośrednie użycie liczb całkowitych.
2. Zaimplementuj FixedPoint64 w C #. Wydało mi się to raczej trudne. W przypadku niektórych operacji przydatne byłyby pośrednie liczby całkowite 128-bitowe. Ale .net nie oferuje takiego typu.
3. Zaimplementuj niestandardowy 32-bitowy zmiennoprzecinkowy. Brak wewnętrznego elementu BitScanReverse powoduje kilka niedogodności przy wdrażaniu tego. Ale obecnie myślę, że to najbardziej obiecująca ścieżka.
4. Użyj kodu natywnego do operacji matematycznych. Obejmuje narzut wywołania delegata w przypadku każdej operacji matematycznej.

Właśnie zacząłem implementację oprogramowania 32-bitowej matematyki zmiennoprzecinkowej. Może zrobić około 70 milionów dodań / mnożenia na sekundę na moim i3 2,66 GHz. https://github.com/CodesInChaos/SoftFloat . Oczywiście nadal jest bardzo niekompletny i wadliwy.

Specyfikacja C # (§4.1.6 Typy zmiennoprzecinkowe) w szczególności umożliwia wykonywanie obliczeń zmiennoprzecinkowych z dokładnością wyższą niż wynik. Więc nie, nie sądzę, aby można było dokonać tych obliczeń bezpośrednio w .Net. Inni sugerowali różne obejścia, więc możesz je wypróbować.

Następna strona może być przydatna w przypadku, gdy potrzebujesz absolutnej przenośności takich operacji. Omawia oprogramowanie do testowania implementacji standardu IEEE 754, w tym oprogramowanie do emulacji operacji zmiennoprzecinkowych. Jednak większość informacji jest prawdopodobnie specyficzna dla C lub C ++.

http://www.math.utah.edu/~beebe/software/ieee/

Uwaga o punkcie stałym

Binarne liczby stałoprzecinkowe mogą również działać jako substytut zmiennoprzecinkowych, jak wynika z czterech podstawowych operacji arytmetycznych:

• Dodawanie i odejmowanie są trywialne. Działają tak samo jak liczby całkowite. Po prostu dodaj lub odejmij!
• Aby pomnożyć dwie liczby ustalone, pomnóż te dwie liczby, a następnie przesuń w prawo określoną liczbę bitów ułamkowych.
• Aby podzielić dwie liczby ustalone, przesuń dywidendę w lewo o określoną liczbę bitów ułamkowych, a następnie podziel przez dzielnik.
• Rozdział czwarty tego artykułu zawiera dodatkowe wskazówki dotyczące implementacji binarnych liczb stałych.

Binarne liczby z punktami stałymi można zaimplementować na dowolnym typie danych całkowitych, takim jak int, long i BigInteger, a także w typach uint i ulong niezgodnych z CLS.

Jak zasugerowano w innej odpowiedzi, możesz użyć tabel przeglądowych, w których każdy element w tabeli jest binarną liczbą stałą punktową, aby pomóc w implementacji złożonych funkcji, takich jak sinus, cosinus, pierwiastek kwadratowy i tak dalej. Jeśli tabela przeglądowa jest mniej szczegółowa niż stała liczba punktów, zaleca się zaokrąglić dane wejściowe przez dodanie połowy szczegółowości tabeli przeglądowej do danych wejściowych:

// Assume each number has a 12 bit fractional part. (1/4096)
// Each entry in the lookup table corresponds to a fixed point number
//  with an 8-bit fractional part (1/256)
input+=(1<<3); // Add 2^3 for rounding purposes
input>>=4; // Shift right by 4 (to get 8-bit fractional part)
// --- clamp or restrict input here --
// Look up value.
return lookupTable[input];

Czy to problem dla C #?

Tak. Różne architektury są najmniejszym z Twoich zmartwień, różne liczby klatek na sekundę itp. Mogą prowadzić do odchyleń z powodu niedokładności w reprezentacjach typu float - nawet jeśli są to te same niedokładności (np. Ta sama architektura, z wyjątkiem wolniejszego GPU na jednym komputerze).

Czy mogę używać System.Decimal?

Nie ma powodu, dla którego nie możesz, jednak jest to pies powolny.

Czy istnieje sposób, aby zmusić mój program do działania z podwójną precyzją?

Tak. Hostuj środowisko wykonawcze CLR samodzielnie ; i skompiluj wszystkie niezbędne wywołania / flagi (które zmieniają zachowanie arytmetyki zmiennoprzecinkowej) do aplikacji C ++ przed wywołaniem CorBindToRuntimeEx.

Czy istnieją biblioteki, które pomogłyby zachować spójność obliczeń zmiennoprzecinkowych?

Nie żebym o tym wiedział.

Czy jest inny sposób rozwiązania tego problemu?

Już wcześniej zajmowałem się tym problemem, chodzi o to, aby użyć QNumbers . Są formą rzeczywistych, które są stałe; ale nie stały punkt w podstawie 10 (dziesiętnie) - raczej podstawa 2 (binarna); z tego powodu matematyczne prymitywy na nich (add, sub, mul, div) są znacznie szybsze niż naiwne ustalone punkty bazowe 10; zwłaszcza jeśli njest taki sam dla obu wartości (co w twoim przypadku tak by było). Ponadto, ponieważ są integralne, mają dobrze zdefiniowane wyniki na każdej platformie.

Pamiętaj, że liczba klatek na sekundę może nadal na nie wpływać, ale nie jest tak zła i można ją łatwo naprawić za pomocą punktów synchronizacji.

Czy mogę używać więcej funkcji matematycznych w QNumbers?

Tak, w tym celu należy użyć liczby dziesiętnej w obie strony. Co więcej, naprawdę powinieneś używać tabel przeglądowych dla funkcji trygonometrycznych (sin, cos); ponieważ mogą one naprawdę dawać różne wyniki na różnych platformach - a jeśli prawidłowo je zakodujesz, będą mogły bezpośrednio używać numerów QNumbers.

Zgodnie z tym nieco starym wpisem na blogu MSDN, JIT nie będzie używać SSE / SSE2 dla zmiennoprzecinkowych, to wszystko jest x87. Z tego powodu, jak wspomniałeś, musisz martwić się o tryby i flagi, aw C # nie można tego kontrolować. Zatem używanie normalnych operacji zmiennoprzecinkowych nie gwarantuje dokładnie tego samego wyniku na każdej maszynie dla twojego programu.

Aby uzyskać dokładną powtarzalność podwójnej precyzji, będziesz musiał wykonać programową emulację zmiennoprzecinkową (lub stałą). Nie znam bibliotek C #, aby to zrobić.

W zależności od potrzebnych operacji możesz być w stanie uciec z pojedynczą precyzją. Oto pomysł:

• przechowuj wszystkie wartości, na których Ci zależy, w jednej precyzji
• aby wykonać operację:
  • rozszerzyć dane wejściowe do podwójnej precyzji
  • działają z podwójną precyzją
  • przekonwertować wynik z powrotem na pojedynczą precyzję

Duży problem z x87 polega na tym, że obliczenia mogą być wykonywane z dokładnością 53-bitową lub 64-bitową, w zależności od flagi precyzji i tego, czy rejestr został rozlany do pamięci. Jednak w przypadku wielu operacji wykonanie operacji z dużą precyzją i zaokrąglenie z powrotem do niższej precyzji zagwarantuje poprawną odpowiedź, co oznacza, że ​​odpowiedź będzie taka sama we wszystkich systemach. To, czy uzyskasz dodatkową precyzję, nie ma znaczenia, ponieważ masz wystarczającą precyzję, aby zagwarantować właściwą odpowiedź w obu przypadkach.

Operacje, które powinny działać w tym schemacie: dodawanie, odejmowanie, mnożenie, dzielenie, sqrt. Rzeczy takie jak sin, exp itp. Nie będą działać (wyniki zwykle będą zgodne, ale nie ma gwarancji). „Kiedy podwójne zaokrąglanie jest nieszkodliwe?” Numer referencyjny ACM (wymaganie płatnej rejestracji)

Mam nadzieję że to pomoże!

Jak już stwierdzono w innych odpowiedziach: Tak, jest to problem w C # - nawet przy zachowaniu czystego systemu Windows.

Jeśli chodzi o rozwiązanie: możesz całkowicie zmniejszyć problem (i przy pewnym wysiłku / wydajności) całkowicie uniknąć problemu, jeśli użyjesz wbudowanej BigIntegerklasy i skalujesz wszystkie obliczenia z określoną precyzją, używając wspólnego mianownika dla dowolnego obliczenia / przechowywania takich liczb.

Zgodnie z życzeniem OP - w zakresie wydajności:

System.Decimalreprezentuje liczbę z 1 bitem na znak i 96-bitową liczbą całkowitą oraz „skalą” (reprezentującą miejsce przecinka). Dla wszystkich wykonywanych obliczeń musi działać na tej strukturze danych i nie może używać żadnych instrukcji zmiennoprzecinkowych wbudowanych w procesor.

BigInteger„Rozwiązanie” czy coś podobnego - tylko, że można określić ile cyfr musisz / chcesz ... może chcesz tylko 80 bitów lub 240 bitów precyzją.

Powolność zawsze wynika z konieczności symulowania wszystkich operacji na tej liczbie za pomocą instrukcji zawierających wyłącznie liczby całkowite bez użycia instrukcji wbudowanych w CPU / FPU, co z kolei prowadzi do znacznie większej liczby instrukcji na operację matematyczną.

Aby zmniejszyć wpływ na wydajność, istnieje kilka strategii - takich jak QNumbers (patrz odpowiedź Jonathana Dickinsona - Czy matematyka zmiennoprzecinkowa jest spójna w C #? Czy może być? ) I / lub buforowanie (na przykład obliczenia trygonometryczne ...) itd.

Cóż, oto moja pierwsza próba, jak to zrobić :

1. Utwórz projekt ATL.dll zawierający prosty obiekt do wykorzystania w krytycznych operacjach zmiennoprzecinkowych. upewnij się, że skompilowałeś go z flagami, które wyłączają używanie sprzętu innego niż xx87 do wykonywania operacji zmiennoprzecinkowych.
2. Twórz funkcje, które wywołują operacje zmiennoprzecinkowe i zwracają wyniki; zacznij od prostego, a jeśli to działa dla Ciebie, zawsze możesz zwiększyć złożoność, aby później spełnić swoje potrzeby wydajnościowe, jeśli to konieczne.
3. Umieść wywołania control_fp wokół rzeczywistej matematyki, aby upewnić się, że jest to robione w ten sam sposób na wszystkich komputerach.
4. Odwołaj się do nowej biblioteki i sprawdź, czy działa zgodnie z oczekiwaniami.

(Uważam, że możesz po prostu skompilować do 32-bitowego .dll, a następnie użyć go z x86 lub AnyCpu [lub prawdopodobnie tylko na x86 w systemie 64-bitowym; patrz komentarz poniżej]).

Następnie zakładając, że to zadziała, czy chcesz użyć Mono Wyobrażam sobie, że powinieneś być w stanie replikować bibliotekę na innych platformach x86 w podobny sposób (nie COM oczywiście; chociaż może z winem? Trochę poza moim obszarem raz chodzimy tam jednak ...).

Zakładając, że możesz sprawić, że to zadziała, powinieneś być w stanie skonfigurować niestandardowe funkcje, które mogą wykonywać wiele operacji naraz, aby naprawić wszelkie problemy z wydajnością, a będziesz mieć matematykę zmiennoprzecinkową, która pozwoli uzyskać spójne wyniki na różnych platformach przy minimalnej ilości kodu napisanego w C ++ i pozostawiając resztę kodu w C #.

Nie jestem programistą gier, chociaż mam duże doświadczenie z problemami trudnymi obliczeniowo ... więc postaram się jak najlepiej.

Strategia, którą przyjąłbym jest zasadniczo taka:

• Użyj wolniejszej (jeśli to konieczne; jeśli istnieje szybszy sposób, świetnie!), Ale przewidywalnej metody, aby uzyskać powtarzalne wyniki
• Użyj double do wszystkiego innego (np. Renderowania)

Krótko i długo to: musisz znaleźć równowagę. Jeśli poświęcasz 30 ms na renderowanie (~ 33 kl./s) i tylko 1 ms na wykrywanie kolizji (lub wstawisz inną bardzo czułą operację) - nawet jeśli potroisz czas potrzebny na wykonanie krytycznej arytmetyki, wpływ to na szybkość klatek jest spadasz z 33,3 kl./s do 30,3 kl./s.

Proponuję profilować wszystko, brać pod uwagę, ile czasu zajmuje wykonanie każdego z zauważalnie kosztownych obliczeń, a następnie powtórzyć pomiary z 1 lub więcej metodami rozwiązania tego problemu i zobaczyć, jaki jest wpływ.

Sprawdzanie linków w innych odpowiedziach daje jasno do zrozumienia, że ​​nigdy nie będziesz mieć gwarancji, czy zmiennoprzecinkowe są „poprawnie” zaimplementowane lub czy zawsze otrzymasz określoną precyzję dla danego obliczenia, ale być może mógłbyś dołożyć wszelkich starań, (1) obcięcie wszystkich obliczeń do wspólnego minimum (np. Jeśli różne implementacje dadzą ci 32 do 80 bitów precyzji, zawsze skracając każdą operację do 30 lub 31 bitów), (2) mieć tabelę kilku przypadków testowych przy starcie (przypadki graniczne dodawania, odejmowania, mnożenia, dzielenia, sqrt, cosinus itp.) i jeśli implementacja oblicza wartości pasujące do tabeli, nie przejmuj się wprowadzaniem żadnych korekt.

Twoje pytanie w dość trudnych i technicznych sprawach O_o. Jednak mogę mieć pomysł.

Na pewno wiesz, że procesor dokonuje pewnych korekt po wszelkich operacjach pływających. A procesor oferuje kilka różnych instrukcji, które wykonują różne operacje zaokrąglania.

Zatem dla wyrażenia Twój kompilator wybierze zestaw instrukcji, które doprowadzą Cię do wyniku. Ale każdy inny przepływ pracy z instrukcjami, nawet jeśli zamierzają obliczyć to samo wyrażenie, może dać inny wynik.

„Błędy” popełniane przez zaokrąglanie będą rosły wraz z każdą kolejną instrukcją.

Na przykład możemy powiedzieć, że na poziomie zespołu: a * b * c nie jest równoważne a * c * b.

Nie jestem tego do końca pewien, będziesz musiał zapytać kogoś, kto zna architekturę procesora dużo lepiej niż ja: str

Jednak odpowiadając na twoje pytanie: w C lub C ++ możesz rozwiązać swój problem, ponieważ masz pewną kontrolę nad kodem maszynowym generowanym przez twój kompilator, jednak w .NET nie masz żadnej. Tak długo, jak twój kod maszynowy może być inny, nigdy nie będziesz pewien dokładnego wyniku.

Jestem ciekawy, w jaki sposób może to być problem, ponieważ zmienność wydaje się bardzo minimalna, ale jeśli potrzebujesz naprawdę dokładnej operacji, jedynym rozwiązaniem, o którym mogę pomyśleć, będzie zwiększenie rozmiaru twoich rejestrów pływających. Jeśli możesz, użyj podwójnej precyzji lub nawet długiego double (nie jesteś pewien, czy jest to możliwe przy użyciu CLI).

Mam nadzieję, że wyraziłem się wystarczająco jasno, nie jestem doskonały z angielskiego (... w ogóle: s)