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

155

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?

BlueRaja - Danny Pflughoeft
źródło
Widziałem to pytanie , ale każda odpowiedź albo powtarza problem bez rozwiązania, albo mówi „zignoruj ​​to”, co nie wchodzi w grę. Zadałem podobne pytanie na gamedevie , ale (ze względu na publiczność) większość odpowiedzi wydaje się być nastawiona na C ++.
BlueRaja - Danny Pflughoeft
1
nie odpowiedź, ale jestem pewien, że w większości dziedzin można zaprojektować system w taki sposób, że wszystkie wspólne państwo jest deterministyczny, a nie ma znaczące pogorszenie wydajności z tego powodu
driushkin
1
@Peter, czy znasz jakąś szybką emulację zmiennoprzecinkową dla .net?
CodesInChaos
1
Czy Java cierpi na ten problem?
Josh
3
@Josh: Java ma strictfpsłowo kluczowe, które wymusza wykonywanie wszystkich obliczeń w określonym rozmiarze ( floatlub double), 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.
porges

Odpowiedzi:

52

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.

CodesInChaos
źródło
2
jest dostępna liczba całkowita o „nieograniczonym” rozmiarze BigInteger, chociaż nie jest tak szybka jak natywna int lub long, więc .NET oferuje taki typ (stworzony dla F #, jak sądzę, ale może być używany w C #)
Rune FS
Inną opcją jest opakowanie GNU MP dla .NET . Jest to opakowanie wokół biblioteki GNU Multiple Precision Library, która obsługuje „nieskończone” precyzyjne liczby całkowite, wymierne (ułamki) i liczby zmiennoprzecinkowe.
Cole Johnson,
2
Jeśli masz zamiar to zrobić, równie dobrze możesz spróbować decimalnajpierw, ponieważ jest to o wiele prostsze. Tylko jeśli jest zbyt wolny dla danego zadania, warto pomyśleć o innych podejściach.
Roman Starkov
Dowiedziałem się o jednym szczególnym przypadku, w którym zmiennoprzecinkowe są deterministyczne. Wyjaśnienie, które otrzymałem, to: W przypadku mnożenia / dzielenia, jeśli jedna z liczb FP jest potęgą dwóch liczb (2 ^ x), wartość znacząca / mantysa nie zmieni się podczas obliczania. Zmieni się tylko wykładnik (punkt się przesunie). Więc zaokrąglanie nigdy się nie wydarzy. Wynik będzie deterministyczny.
zygzak
Przykład: liczba taka jak 2 ^ 32 jest reprezentowana jako (wykładnik: 32, mantysa: 1). Jeśli pomnożymy to przez inny float (exp, man), otrzymamy (exp + 32, man * 1). W przypadku podziału wynikiem jest (expo - 32, człowiek * 1). Pomnożenie mantysy przez 1 nie zmienia mantysy, więc nie ma znaczenia, ile ma bitów.
zygzak
28

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ć.

svick
źródło
9
Właśnie zdałem sobie sprawę, że specyfikacja C # tak naprawdę nie ma znaczenia, jeśli dystrybuuje się skompilowane zestawy. Ma to znaczenie tylko wtedy, gdy chce się zgodności ze źródłami. To, co naprawdę ma znaczenie, to specyfikacja CLR. Ale jestem prawie pewien, że gwarancje są tak samo słabe, jak gwarancje C #.
CodesInChaos
Czy rzutowanie do za doublekażdym razem po operacji nie usuwałoby niechcianych bitów, dając spójne wyniki?
IllidanS4 chce, aby Monica wróciła
2
@ IllidanS4 Nie sądzę, żeby to gwarantowało spójne wyniki.
svick
14

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];
Peter O.
źródło
5
Powinieneś przesłać to do witryny projektu o otwartym kodzie źródłowym, takiej jak sourceforge lub github. Ułatwia to znalezienie, łatwiejsze wnoszenie wkładu, łatwiejsze umieszczanie CV itp. Ponadto kilka wskazówek dotyczących kodu źródłowego (możesz zignorować): Użyj constzamiast staticstałych, aby kompilator mógł je zoptymalizować; wolą funkcje składowe od funkcji statycznych (abyśmy mogli wywoływać np. myDouble.LeadingZeros()zamiast IntDouble.LeadingZeros(myDouble)); staraj się unikać nazw zmiennych MultiplyAnyLengthskładających się z jednej litery ( na przykład ma 9, co bardzo utrudnia śledzenie)
BlueRaja - Danny Pflughoeft
Bądź ostrożny przy użyciu uncheckedi nie-CLS-zgodne typy, takie jak ulong, uintitp 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 jak longi int. 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!
BlueRaja - Danny Pflughoeft
Dziękuję za komentarze. Wykonuję testy jednostkowe kodu. Są one jednak dość obszerne, zbyt obszerne, aby na razie je opublikować. Piszę nawet procedury pomocnicze do testów jednostkowych, aby ułatwić pisanie wielu testów. Na razie nie używam przeciążonych operatorów, ponieważ mam plany przetłumaczenia kodu na Javę, kiedy skończę.
Peter O.
2
Zabawne jest to, że kiedy pisałem na twoim blogu, nie zauważyłem, że blog jest twój. Właśnie zdecydowałem się wypróbować Google + iw swojej iskrze C # zasugerowałem ten wpis na blogu. Pomyślałem więc: „Cóż za niezwykły zbieg okoliczności, że w tym samym czasie zaczęliśmy pisać coś takiego”. Ale oczywiście mieliśmy ten sam wyzwalacz :)
CodesInChaos
1
Po co zawracać sobie głowę przenoszeniem tego na Javę? Java ma już gwarantowaną deterministyczną matematykę zmiennoprzecinkową za pośrednictwem strictfp.
Antymon
9

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.

Jonathan Dickinson
źródło
3
Nie jestem pewien, o czym mówisz, skoro występują problemy z liczbą klatek na sekundę. Oczywiście chciałbyś mieć stałą częstotliwość odświeżania (patrz na przykład tutaj ) - nie ma znaczenia, czy jest to to samo, co liczba klatek na sekundę na ekranie. Tak długo, jak niedokładności są takie same na wszystkich maszynach, jesteśmy w porządku. W ogóle nie rozumiem twojej trzeciej odpowiedzi.
BlueRaja - Danny Pflughoeft
@BlueRaja: Odpowiedź "Czy istnieje sposób, aby zmusić mój program do działania z podwójną precyzją?" oznaczałoby albo ponowne zaimplementowanie całego środowiska uruchomieniowego języka wspólnego, co byłoby niezwykle skomplikowane, albo użycie natywnych wywołań biblioteki DLL C ++ z aplikacji C #, jak zasugerowano w odpowiedzi użytkownika shelleybutterfly. Pomyśl o „QNumbers” jedynie jako o binarnych liczbach stałych punktów, jak zasugerowałem w mojej odpowiedzi (do tej pory nie widziałem binarnych liczb stałych nazywane „QNumbers”).
Peter O.
@Pieter O. Nie musisz ponownie wdrażać środowiska wykonawczego. Serwer, na którym pracuję w mojej firmie, obsługuje środowisko wykonawcze CLR jako natywną aplikację C ++ (podobnie jak SQL Server). Proponuję wygooglować CorBindToRuntimeEx.
Jonathan Dickinson
@BlueRaja to zależy od danej gry. Stosowanie stałej liczby klatek na sekundę do wszystkich gier nie jest realną opcją - ponieważ algorytm AOE wprowadza sztuczne opóźnienie; co jest niedopuszczalne np. w FPS.
Jonathan Dickinson
1
@Jonathan: Jest to problem tylko w grach peer-to-peer, które wysyłają tylko dane wejściowe - w takich przypadkach musisz mieć stałą częstotliwość aktualizacji. Większość FPS-ów nie działa w ten sposób, ale kilka, które muszą mieć stałą częstotliwość aktualizacji. Zobacz to pytanie .
BlueRaja - Danny Pflughoeft,
6

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!

Nathan Whitehead
źródło
2
Problemem jest również to, że .NET 5, 6 lub 42 mogą już nie używać trybu obliczeń x87. W standardzie nie ma niczego, co by tego wymagało.
Eric J.
5

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.

Yahia
źródło
1
Należy pamiętać, że BigIntegerjest to dostępne tylko w .Net 4.0.
Svick,
Domyślam się, że wydajność hitów BigIntegerprzewyższa nawet wydajność osiągniętą przez Decimal.
CodesInChaos
Kilka razy w odpowiedziach tutaj pojawia się odniesienie do hitu wydajnościowego używania Decimal(@Jonathan Dickinson - `` dog slow '') lub BigInteger(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.
Barry Kaye
@Yahia - dziękuję za edycję - ciekawa lektura, ale czy mógłbyś tylko dać oszacowanie wydajności nieużywania `` float '', czy mówimy 10% wolniej, czy 10 razy wolniej - po prostu chcą wczuć się w sugerowany rząd wielkości.
Barry Kaye
bardziej prawdopodobne jest to w obszarze 1: 5 niż „tylko 10%”
Yahia
2

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 #.

shelleybutterfly
źródło
„skompiluj do 32-bitowego pliku .dll, a następnie użyj… AnyCpu” Myślę, że zadziała to tylko w systemie 32-bitowym. W systemie 64-bitowym tylko program docelowy x86będzie mógł załadować 32-bitową bibliotekę dll.
CodesInChaos
2

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.

Brian Vandenberg
źródło
1

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.

mikrofon
źródło
zawsze obcinając każdą operację do 30 lub 31 bitów - to jest dokładnie to, co ten floattyp 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.
BlueRaja - Danny Pflughoeft
Jeśli „N bitów precyzji” oznacza, że ​​jakiekolwiek obliczenia są dokładne do tej liczby bitów, a maszyna A ma dokładność do 32 bitów, podczas gdy maszyna B ma dokładność do 48 bitów, to pierwsze 32 bity dowolnego obliczenia obliczonego przez obie maszyny powinny być identyczne. Czy obcięcie do 32 bitów lub mniej po każdej operacji nie zapewniłoby dokładnej synchronizacji obu maszyn? Jeśli nie, jaki jest przykład?
Dowód tożsamości świadka 44583292
-3

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)

AxFab
źródło
9
Wyobraź sobie strzelankę P2P. Strzelasz do faceta, uderzasz go i on ginie, ale jest bardzo blisko, prawie nie trafiłeś. Na komputerze drugiego gościa oblicza się nieco inaczej i oblicza, że ​​przegapiłeś. Czy widzisz teraz problem? W takim przypadku zwiększenie rozmiaru rejestrów nie pomoże (przynajmniej nie do końca). Używając dokładnie tych samych obliczeń na każdym komputerze.
svick
5
W tym scenariuszu zwykle nie przejmuje się tym, jak blisko jest wynik do rzeczywistego wyniku (o ile jest to rozsądne), ale ważne jest to, że jest dokładnie taki sam dla wszystkich użytkowników.
CodesInChaos
1
Masz rację, nie myślałem o takim scenariuszu. Jednak zgadzam się z @CodeInChaos w tej sprawie. Nie wydaje mi się, aby dwukrotnie podejmować ważną decyzję. Jest to bardziej kwestia architektury oprogramowania. Jeden program, na przykład aplikacja strzelca, powinien dokonać obliczenia i przesłać wynik do innych. W ten sposób nigdy nie będziesz mieć błędów. Masz trafienie lub nie, ale tylko jeden podejmuje decyzję. Na przykład powiedz @driushkin
AxFab
2
@Aesgar: Tak, tak działa większość strzelców; ten „autorytet” jest nazywany serwerem, a ogólną architekturę nazywamy architekturą „klient / serwer”. Jest jednak inny rodzaj architektury: peer-to-peer. W P2P nie ma serwera; raczej wszyscy klienci muszą zweryfikować wszystkie działania ze sobą, zanim cokolwiek się stanie. Zwiększa to opóźnienie, przez co jest nie do przyjęcia dla strzelanek, ale znacznie zmniejsza ruch sieciowy, co czyni go idealnym do gier, w których małe opóźnienie (~ 250 ms) jest dopuszczalne, ale synchronizacja całego stanu gry nie. Mianowicie gry RTS, takie jak C&C i Starcraft, używają P2P.
BlueRaja - Danny Pflughoeft
5
W grze p2p nie masz zaufanej maszyny, na której możesz polegać. Jeśli pozwolisz jednej stacji zdecydować, czy jego kula trafiła, czy nie, otwierasz możliwość oszukiwania klienta. Co więcej, linki nie mogą nawet obsłużyć ilości danych, które czasami wynikają - gry działają, wysyłając zamówienia, a nie wyniki. Gram w gry RTS i wiele razy widziałem tyle śmieci latających wokół, że nie można ich wysłać przez zwykłe domowe łącza nadrzędne.
Loren Pechtel,