Jak działa ten algorytm aproksymacji podziału?

Question

Pracuję nad grą z renderem oprogramowania, aby uzyskać jak najdokładniejszy wygląd PS1. Kiedy robiłem badania nad tym, jak działał system grafiki/renderowania PS1, powód chybotliwych wierzchołków itp., Natknąłem się na pewną dokumentację dotyczącą sposobu, w jaki dokonali podziału. Oto link do niego: http://problemkaputt.de/psx-spx.htm#gteoverview (patrz „GTE Division Niedokładność” fragment)

Odpowiedni kod:

if (H < SZ3*2) then       ;check if overflow 
    z = count_leading_zeroes(SZ3)    ;z=0..0Fh (for 16bit SZ3) 
    n = (H SHL z)        ;n=0..7FFF8000h 
    d = (SZ3 SHL z)        ;d=8000h..FFFFh 
    u = unr_table[(d-7FC0h) SHR 7] + 101h  ;u=200h..101h 
    d = ((2000080h - (d * u)) SHR 8)    ;d=10000h..0FF01h 
    d = ((0000080h + (d * u)) SHR 8)    ;d=20000h..10000h 
    n = min(1FFFFh, (((n*d) + 8000h) SHR 16)) ;n=0..1FFFFh 
    else n = 1FFFFh, FLAG.Bit17=1, FLAG.Bit31=1 ;n=1FFFFh plus overflow flag 

Mam twardy czas zrozumienia, jak to działa, co to jest „UNR ' stół? dlaczego zmieniamy rzeczy? Jeśli ktoś mógłby podać bardziej szczegółowe wyjaśnienie, w jaki sposób ta rzecz faktycznie osiąga podział, byłoby to docenione.

Answer 1

Algorytm ten jest stałym podziałem dwóch niepodpisanych 16-bitowych wartości ułamkowych w [0,1). Najpierw oblicza wstępną 9-bitową aproksymację do odwrotności dzielnika za pomocą przeszukiwania tabeli, doprecyzowuje ją przy pomocy pojedynczej iteracji Newtona-Raphsona dla odwrotności, x _{i + 1}: = xi = 0 * (2 - d * x _i), w wyniku czego dokładność odwrotna do około 16 bitów, ostatecznie mnoży to przez dywidendę, dając 17-bitowy współczynnik w [0,2).

Przy wyszukiwaniu tabeli dzielnik jest najpierw normalizowany na [0,5, 1) przez zastosowanie współczynnika skalowania 2 ^z, oczywiście dywidenda musi być następnie skorygowana o taki sam współczynnik skali. Ponieważ odwrotność argumentów w [0.5, 1), będzie wynosić [1,2], bit całkowity odwrotności jest znany jako 1, więc można użyć 8-bitowych wpisów w tabeli, aby wytworzyć 1.8 punktu stałego odwrotność przez dodanie 0x100 (= 1). Powód 0x101 jest tutaj użyty, nie jest jasny; może to wynikać z wymogu, że ten krok zawsze zapewnia zawyżenie prawdziwej wzajemności.

Kolejne dwa kroki to dosłowne tłumaczenia iteracji Newtona-Raphsona dla odwrotności z uwzględnieniem stałych współczynników skali. Tak więc 0x2000000 reprezentuje 2.0. Kod używa 0x2000080, ponieważ zawiera stałą zaokrąglania 0x80 (= 128) dla następnego podziału przez 256, używaną do przeskalowania wyniku. Następny krok również dodaje 0x00000080 jako stałą zaokrąglania dla podziału skalowania o 256. Bez skalowania byłoby to czyste mnożenie.

Ostateczne pomnożenie n*d zwielokrotnia odwłok w d z dywidendą w n, aby uzyskać iloraz w 33 bitach. Ponownie, stała zaokrąglania 0x8000 jest stosowana przed dzieleniem przez 65536, aby przeskalować do właściwego zakresu, podając iloraz w formacie 1.16 stałoprzecinkowym.

Ciągłe przeskalowywanie jest typowe dla obliczeń stałoprzecinkowych, gdy próbuje się uzyskać możliwie jak największe wyniki pośrednie, aby zmaksymalizować dokładność końcowego wyniku. Nieco niezwykłe jest to, że zaokrąglanie jest stosowane we wszystkich arytmetyce pośredniej, a nie tylko w ostatnim kroku. Być może konieczne było osiągnięcie określonego poziomu dokładności.

Funkcja ta nie jest jednak dokładna, co prawdopodobnie wynika z niedokładności wstępnego przybliżenia. We wszystkich nie wyjątkowych przypadkach 2,424,807,756 pasuje do prawidłowo zaokrąglonego 1,16 punktu stałego, 780,692,403 ma błąd równy 1 ulp, 15 606,093 ma błąd 2-ulp, a 86 452 ma błąd 3-ulp. W szybkim eksperymencie, maksymalny błąd w początkowym przybliżeniu u wynosił 3,89e-3. Poprawione wyszukiwanie w tabeli zmniejsza maksymalny błąd względny w u do 2.85e-3, redukując, ale nie eliminując błędów 3-ulp w wyniku końcowym.

Jeśli chcesz spojrzeć na konkretnym przykładzie, należy rozważyć h = 0,3 (0x4ccd) podzielonej przez SZ3 = 0,2 (0x3333). Następnie z = 2, a więc d = 0,2 * 4 = 0,8 (0xcccc). To prowadzi do u = 1,25 (0x140). Ponieważ oszacowanie jest dość dokładne, spodziewamy się, że (2 - d * u) będzie blisko 1, a w rzeczywistości d = 1.000015 (0x10001). Udoskonalona wzajemność wychodzi na d = 1.250015 (0x14001), a iloraz wynosi zatem n = 1,500031 (0x18002).