Mọi điều cần biết về thuật toán nghịch đảo căn bậc hai nhanh

Mọi điều cần biết về thuật toán nghịch đảo căn bậc hai nhanh

Thuật toán

• Thuật toán nghịch đảo căn bậc hai nhanh là thuật toán nổi tiếng nhờ mã nguồn Quake 3, được John Carmack sử dụng.
• Thuật toán này thao tác trên các bit của số dấu phẩy động để tính nghịch đảo căn bậc hai một cách nhanh chóng.
• Ví dụ mã:

  float Q_rsqrt(float number) {
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
  
    x2 = number * 0.5F;
    y = number;
    i = *(long*)&y;              // 부동 소수점 비트 수준 해킹
    i = 0x5f3759df - ( i >> 1 ); // 마법의 상수
    y = *(float*)&i;
    y = y * ( threehalfs - ( x2 * y * y ) );  // 1차 반복
  
    return y;
  }
  

Số dấu phẩy động 32 bit: biểu diễn

• Số dấu phẩy động IEEE-754 32 bit gồm 3 thành phần:
  • Dấu: 1 bit, cho biết số là dương hay âm.
  • Số mũ: 8 bit, quyết định phạm vi của số.
  • Phần trị: 23 bit, xác định vị trí của số trong phạm vi đó.
• Giá trị thực được tính như sau:

  N = -1^S * 2^(E-127) * (1 + M/2^23)
  

Số dấu phẩy động 32 bit: diễn giải bit

• Biểu diễn nội bộ của số dấu phẩy động thường không quan trọng với lập trình viên.
• Tuy nhiên, nếu hiểu rõ cách biểu diễn này thì có thể thiết kế được các thuật toán hiệu quả.
• Nếu diễn giải mẫu bit của số dấu phẩy động như một số nguyên, ta sẽ thu được giá trị xấp xỉ của hàm log.

  log2(x) ≈ Ix / L - B
  

Phương pháp Newton

• Để cải thiện giá trị xấp xỉ ban đầu, người ta sử dụng phương pháp Newton (Newton's method).
• Phương pháp Newton là thuật toán lặp để liên tục cải thiện giá trị gần đúng của một hàm đã cho.
• Ví dụ mã:

  y = y * ( threehalfs - ( x2 * y * y ) ); // 1차 반복
  

Kết luận

• Thuật toán này được thiết kế dựa trên sự hiểu biết sâu sắc về các chi tiết toán học bên trong của hệ thống số dấu phẩy động, đồng thời tận dụng những phép toán chạy nhanh trên máy tính.
• Nguồn gốc của thuật toán vẫn chưa chắc chắn, nhưng đây là một ví dụ về kỹ thuật được thiết kế rất hiệu quả và khéo léo.

Ý kiến của GN⁺

• Tầm quan trọng lịch sử: Đây là một phương pháp mang tính đột phá, được tạo ra כדי vượt qua các hạn chế phần cứng vào thời điểm đó.
• Giá trị giáo dục: Rất hữu ích để hiểu cấu trúc bên trong của số dấu phẩy động và các nguyên lý toán học liên quan.
• Ứng dụng hiện đại: Trên phần cứng hiện đại, nó có thể ít cần thiết hơn, nhưng nguyên lý của thuật toán vẫn hữu ích.
• Khả năng tối ưu hóa: Giá trị hằng số của thuật toán có thể được tối ưu thêm, và đây vẫn là chủ đề còn chỗ cho nghiên cứu.
• Góc nhìn phản biện: Trên phần cứng hiện đại có thể đã có những phương pháp tốt hơn, vì vậy luôn cần so sánh với công nghệ mới nhất.

[joyfui]

Đoạn code thú vị lâu lâu lại được nhắc đến.. hehe

[GN⁺]

Ý kiến trên Hacker News

• Hỗ trợ lệnh SSE: Các máy tính được sản xuất sau năm 1999 hỗ trợ tập lệnh SSE, và có thể tính nghịch đảo căn bậc hai rất nhanh thông qua lệnh _mm_rsqrt_ps.

• Sự phát triển của phần cứng hiện đại: Trên phần cứng hiện đại, phép tính nghịch đảo căn bậc hai có thể được thực hiện nhanh trên CPU, và việc offload mọi phép toán dấu phẩy động sang GPU là một hiểu lầm.

• Triển khai bằng MMIX: Có mã ví dụ triển khai phép tính nghịch đảo căn bậc hai bằng ngôn ngữ MMIX. Đoạn mã này giả định ban đầu rằng số gốc lớn hơn 2^-1021.

• Lỗi đánh máy trong công thức: Có lỗi đánh máy trong công thức dấu phẩy động. Cần sửa thành (-1)^S.

• Diễn giải log: Việc diễn giải mẫu bit thô không phải là xấp xỉ tuyến tính từng đoạn của log. Các đường thẳng giữa các điểm dữ liệu thực ra không tồn tại.

• Tham khảo Wikipedia: Có một phần thảo luận hay trên Wikipedia về hàm này và lịch sử của nó. Liên kết Wikipedia

• Tổng hợp mã trên GitHub: Một số đoạn mã liên quan đã được tổng hợp trên GitHub. Liên kết GitHub

• Tham khảo StackOverflow: Cũng đáng xem câu hỏi trên StackOverflow về phép xấp xỉ tối ưu độ chính xác thấp. Liên kết StackOverflow

• Kinh nghiệm tối ưu hóa engine 3D: Đã tích lũy kinh nghiệm tối ưu hóa khi xây dựng engine 3D từ trước thời Quake, và tối ưu hóa thuật toán luôn là yếu tố chiến thắng.

• Đề xuất video YouTube: Có một video thú vị về chủ đề này. Liên kết YouTube

• Kẻ đánh cắp thời gian năng suất: Đã bị cuốn vào chủ đề này và mất khá nhiều thời gian lẽ ra có thể làm việc hiệu quả.

• Con số ma thuật tối ưu: Con số ma thuật trong đoạn mã nổi tiếng không phải là hằng số tối ưu. Có thể tìm được hằng số tốt hơn, và có thể dùng Jupyter Notebook để tìm ra con số ma thuật tối ưu.