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
double
obliczenia korzystały z 64-bitowego IEEE-754) przy użyciu_controlfp_s
(Windows),_FPU_SETCW
(Linux?) Lubfpsetprec
(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
float
idouble
całkowicie.decimal
działałby w tym celu, ale byłby znacznie wolniejszy i żadna zSystem.Math
funkcji 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?
strictfp
słowo kluczowe, które wymusza wykonywanie wszystkich obliczeń w określonym rozmiarze (float
lubdouble
), a nie w rozszerzonym rozmiarze. Jednak Java nadal ma wiele problemów ze wsparciem dla IEE-754. Bardzo (bardzo, bardzo) niewiele języków programowania dobrze obsługuje IEE-754.Odpowiedzi:
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
float
sw deterministycznym kodzie .net nie jest możliwe.Rozwiązania, które rozważałem:
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.
źródło
decimal
najpierw, ponieważ jest to o wiele prostsze. Tylko jeśli jest zbyt wolny dla danego zadania, warto pomyśleć o innych podejściach.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ć.
źródło
double
każdym razem po operacji nie usuwałoby niechcianych bitów, dając spójne wyniki?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:
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:
źródło
const
zamiaststatic
stałych, aby kompilator mógł je zoptymalizować; wolą funkcje składowe od funkcji statycznych (abyśmy mogli wywoływać np.myDouble.LeadingZeros()
zamiastIntDouble.LeadingZeros(myDouble)
); staraj się unikać nazw zmiennychMultiplyAnyLength
składających się z jednej litery ( na przykład ma 9, co bardzo utrudnia śledzenie)unchecked
i nie-CLS-zgodne typy, takie jakulong
,uint
itp celach prędkości - ponieważ są one tak rzadko używane, JIT nie optymalizować je jako agresywnie, więc korzystanie z nich w rzeczywistości może być wolniejsze niż przy użyciu zwykłych typów jaklong
iint
. Ponadto język C # ma przeciążenie operatora , na którym ten projekt bardzo by się przydał. Wreszcie, czy są jakieś powiązane testy jednostkowe? Oprócz tych drobiazgów, niesamowita robota Peter, to jest absurdalnie imponujące!strictfp
.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
n
jest 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.
źródło
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ł:
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!
źródło
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
BigInteger
klasy 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.Decimal
reprezentuje 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.
źródło
BigInteger
jest to dostępne tylko w .Net 4.0.BigInteger
przewyższa nawet wydajność osiągniętą przez Decimal.Decimal
(@Jonathan Dickinson - `` dog slow '') lubBigInteger
(komentarz @CodeInChaos powyżej) - czy ktoś może podać trochę wyjaśnienia na temat tych hitów wydajnościowych i czy / dlaczego naprawdę pokazują, jak proponują rozwiązania.Cóż, oto moja pierwsza próba, jak to zrobić :
(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 #.
źródło
x86
będzie mógł załadować 32-bitową bibliotekę dll.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:
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.
źródło
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.
źródło
float
typ danych robi na maszynach x86 - jednak spowoduje to nieco inne wyniki niż maszyny, które wykonują wszystkie obliczenia przy użyciu tylko 32-bitów, a te małe zmiany będą propagować się z czasem. Stąd pytanie.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)
źródło