이 부문 근사 알고리즘은 어떻게 작동합니까?

Question

가장 정확한 PS1 모양을 얻으려면 소프트웨어 렌더러가있는 게임을하고 있습니다. PS1 그래픽/렌더링 시스템이 어떻게 작동했는지, 왜곡 된 꼭지점 등의 이유에 대한 연구를하면서, 나는 그들이 분열 한 방식에 관한 문서를 보았습니다. 여기에 대한 링크입니다 : http://problemkaputt.de/psx-spx.htm#gteoverview (참조는 "GTE 부문 부정확"섹션)

관련 코드 :

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 

나는 이것이 어떻게 작동하는지 이해하기 힘든 시간을 보내고있어,이 'UNR 것입니다 '테이블? 왜 우리가 물건을 바꾼거야? 누군가이 물건이 실제로 어떻게 나누기를 달성하는지에 관해 더 자세한 설명을 줄 수 있다면, 그것은 인정 될 것입니다.

Answer 1

이 알고리즘은 [0,1]의 부호없는 16 비트 분수 값 2 개를 고정 소수점으로 나누는 것입니다. 먼저 테이블 검색을 통해 제수의 역수에 대한 초기 9 비트 근사치를 계산하고 역수에 대한 단일 Newton-Raphson 반복을 사용하여이를 다시 정제합니다. x _{i + 1} : = x _i * (2 - d * x _i), 결과적으로 약 16 비트의 정확도를 가지며 최종적으로 배당을 곱해 [0,2]에서 17 비트 지수를 산출합니다.

테이블 조회의 경우 제수는 먼저 눈금 계수 2 ^z을 적용하여 [0.5, 1]로 정규화됩니다. 분명히 배당은 동일한 배율 인수로 조정해야합니다. [0.5, 1]의 피연산자의 역수는 [1,2]가 될 것이므로 역수의 정수 비트는 1로 알려져 있으므로 8 비트 테이블 항목을 사용하여 1.8 고정 소수점을 생성 할 수 있습니다 0x100 (= 1)을 추가하여 역수로 입력하십시오. 여기서 0x101을 사용하는 이유는 명확하지 않습니다. 이 단계는 항상 진정한 상호의 과대 평가를 제공해야한다는 요구 사항 때문일 수 있습니다.

다음 두 단계는 고정 소수점 스케일 인수를 고려한 역수에 대한 Newton-Raphson 반복의 축 어적 번역입니다. 따라서 0x2000000은 2.0을 나타냅니다. 코드는 0x2000080을 사용합니다. 그 이유는 결과를 다시 스케일링하는 데 사용되는 다음 나누기에 대해 반올림 상수 0x80 (= 128)을 256 씩 통합하기 때문입니다. 다음 단계는 마찬가지로 256으로 리 스케일링 나누기의 반올림 상수로 0x00000080을 추가합니다. 스케일링이 없으면 이것은 순수한 곱셈입니다.

최종 승수 n*d은 d의 역수와 n의 배당금을 곱하여 33 비트의 지수를 산출합니다. 다시 말하지만 0x8000의 반올림 상수는 65536으로 나누기 전에 적용되어 적절한 범위로 다시 조정되어 1.16 고정 소수점 형식의 지수를 부여합니다.

연속 재조정은 최종 결과의 정확성을 극대화하기 위해 중간 결과를 가능한 한 크게 유지하려고하는 고정 소수점 계산의 전형입니다. 약간 특이한 점은 마지막 단계에서가 아니라 모든 중간 산술에 반올림이 적용된다는 것입니다. 아마도 특정 수준의 정확성을 달성해야했습니다.

이 함수는 정확하지는 않지만 초기 근사값의 부정확성에 기인합니다. 예외적이지 않은 모든 경우에서 2,424,807,756은 올바르게 반올림 된 1.16 고정 소수점 결과와 일치하고, 780,692,403은 1 ulp의 오류를 가지며 15,606,093은 2-ulp 오류를 가지며 86,452는 3-ulp 오류를 갖습니다. 빠른 실험에서 상대의 오차는 초기 근사치 u에서 3.89e-3이었습니다. 향상된 테이블 조회는 u의 최대 상대 오류를 2로 줄입니다.85e-3, 최종 결과에서 3-ulp 오류는 줄이지 ​​만 제거하지는 않습니다.

구체적인 예를 보려면 h = 0.3 (0x4ccd)을 SZ3 = 0.2 (0x3333)로 나눈 값을 고려하십시오. 그 다음 z = 2이므로 d = 0.2 * 4 = 0.8 (0xcccc)입니다. 이로 인해 u = 1.25 (0x140)가됩니다. 추정치가 매우 정확하므로 (2 - d * u)는 1에 가까워지고 실제로는 d = 1.000015 (0x10001)가됩니다. 정제 된 역수는 d = 1.250015 (0x14001)로 나오므로, 지수는 n = 1.500031 (0x18002)이됩니다.