Thuật toán xấp xỉ phân chia này hoạt động như thế nào?

Question

Tôi đang làm việc trên một trò chơi với trình kết xuất phần mềm để có giao diện PS1 chính xác nhất. Khi tôi đang nghiên cứu về cách thức hệ thống đồ họa/kết xuất PS1 hoạt động, lý do cho các đỉnh lung lay vv, tôi đã xem qua một số tài liệu liên quan đến cách chúng phân chia. Dưới đây là liên kết với nó: http://problemkaputt.de/psx-spx.htm#gteoverview (xem phần "GTE Division thiếu chính xác" phần)

Mã liên quan:

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 

Tôi đang gặp một thời gian khó khăn để hiểu cách làm việc này, những gì là thế này 'UNR ' bàn? tại sao chúng ta chuyển dịch? Nếu ai đó có thể đưa ra một lời giải thích chi tiết hơn về cách điều này thực sự đạt được sự phân chia, nó sẽ được đánh giá cao.

Answer 1

Thuật toán này là phân chia điểm cố định của hai giá trị phân số 16 bit chưa ký trong [0,1). Đầu tiên nó tính toán một xấp xỉ 9 bit ban đầu với nghịch đảo của số chia thông qua tra cứu bảng, tinh chỉnh điều này với một lần lặp Newton-Raphson cho nghịch đảo, x _{i + 1}: = x _i * (2 - d * x _i), dẫn đến một nghịch đảo chính xác đến khoảng 16 bit, cuối cùng nhân số này bằng cổ tức, sinh ra một thương số 17 bit trong [0,2).

Để tra cứu bảng, ước số được chuẩn hóa đầu tiên thành [0.5, 1) bằng cách áp dụng hệ số tỷ lệ 2 ^z, rõ ràng là cổ tức sau đó cần được điều chỉnh bởi cùng hệ số tỷ lệ. Vì các nghịch đảo của toán hạng trong [0.5, 1), sẽ là [1,2], bit số nguyên của nghịch đảo được biết là 1, vì vậy ta có thể sử dụng các mục bảng 8 bit để tạo ra 1,8 điểm cố định đối ứng bằng cách thêm 0x100 (= 1). Lý do 0x101 được sử dụng ở đây không rõ ràng; nó có thể là do một yêu cầu mà bước này luôn luôn cung cấp một đánh giá quá cao của các đối ứng thực sự.

Hai bước tiếp theo là bản dịch đúng nguyên văn của phép lặp Newton-Raphson cho đối ứng có tính đến các yếu tố thang điểm cố định. Vì vậy, 0x2000000 đại diện cho 2.0. Mã sử ​​dụng 0x2000080 vì nó kết hợp hằng số làm tròn 0x80 (= 128) cho phân chia sau 256, được sử dụng để định lại kết quả. Bước tiếp theo tương tự như vậy, thêm 0x00000080 làm hằng số làm tròn cho một bộ phận thay đổi kích thước 256. Nếu không có tỷ lệ, đây sẽ là phép nhân thuần túy.

Phép nhân cuối cùng n*d nhân số nghịch đảo trong d với số cổ tức trong n để sinh lợi trong 33 bit. Một lần nữa, một hằng số làm tròn của 0x8000 được áp dụng trước khi chia cho 65536 để rescale vào phạm vi thích hợp, đưa ra một thương trong 1,16 định dạng điểm cố định.

Việc định lại lại liên tục là điển hình của tính toán điểm cố định, trong đó người ta cố giữ kết quả trung gian càng lớn càng tốt để tối đa hóa độ chính xác của kết quả cuối cùng. Điều gì là một chút bất thường là làm tròn được áp dụng trong tất cả các số học trung gian, hơn là chỉ trong bước cuối cùng. Có lẽ nó là cần thiết để đạt được một mức độ chính xác được chỉ định.

Chức năng này không phải tất cả chính xác, mặc dù, có thể do thiếu chính xác trong xấp xỉ ban đầu. Trong tất cả các trường hợp không đặc biệt, 2,424,807,756 khớp với kết quả 1.16 điểm cố định được làm tròn chính xác, 780.692.403 có lỗi là 1 ulp, 15,606,093 có lỗi 2-ulp và 86,452 có lỗi 3-ulp. Trong thử nghiệm nhanh, số lỗi tối đa tương đối trong xấp xỉ ban đầu u là 3,89e-3. Tra cứu bảng cải thiện làm giảm lỗi tương đối tối đa trong u thành 2.85e-3, giảm nhưng không loại bỏ các lỗi 3-ulp trong kết quả cuối cùng.

Nếu bạn muốn xem một ví dụ cụ thể, hãy xem xét h = 0,3 (0x4ccd) chia cho SZ3 = 0,2 (0x3333). Sau đó, z = 2, do đó d = 0,2 * 4 = 0,8 (0xcccc). Điều này dẫn đến u = 1.25 (0x140). Vì ước tính là khá chính xác, chúng tôi mong đợi (2 - d * u) ở gần 1 và trên thực tế, d = 1.000015 (0x10001). Giá trị nghịch đảo được tinh chỉnh là d = 1.250015 (0x14001) và do đó thương là n = 1.500031 (0x18002).