Câu chuyện về 0x5f3759df
Câu chuyện về "magic number" 0x5f3759df là một trong những huyền thoại thú vị nhất trong lịch sử lập trình game và khoa học máy tính. Nó liên quan đến một thuật toán cực kỳ thông minh để tính toán căn bậc hai nghịch đảo (fast inverse square root), giúp tăng tốc đáng kể đồ họa 3D.
Bối cảnh: Căn bậc hai nghịch đảo
Trong đồ họa 3D, việc tính toán căn bậc hai nghịch đảo là rất quan trọng. Nó được dùng để chuẩn hóa (normalize) các vector, một bước cần thiết để tính toán ánh sáng (lighting) và bóng đổ (shadows).
Vào những năm 1990, các phép toán dấu phẩy động (floating-point operations) rất tốn thời gian. Mặc dù CPU có lệnh để tính căn bậc hai, chúng lại chậm hơn nhiều so với các phép toán cơ bản khác.
Thuật toán Fast Inverse Square Root
Để giải quyết vấn đề này, các lập trình viên của game Quake III Arena (phát hành năm 1999) đã tạo ra một thuật toán cực kỳ thông minh và nhanh chóng. Thuật toán này không sử dụng phép chia hay căn bậc hai truyền thống mà dựa vào các phép toán bit (bit manipulation) để đưa ra một giá trị xấp xỉ ban đầu, sau đó tinh chỉnh bằng một phép lặp Newton-Raphson.
Nói đơn giản, với một số x bất kỳ, hàm này sẽ trả về giá trị gần đúng nhất với 1/√x. Nghe có vẻ khô khan, nhưng chính nó đã mở ra một kỷ nguyên mới cho đồ họa 3D.
Đây là đoạn mã gốc:
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit hack
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration of Newton's method
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
return y;
}
Dòng nổi tiếng nhất trong đoạn mã này là: i = 0x5f3759df - ( i >> 1 );
Điều thú vị hơn cả là giải pháp này đã nằm im trong các tệp nguồn của Quake ít nhất 5 năm, với nguồn gốc có thể từ những năm 90. Nếu đây là một phát hiện trong giới học thuật, người tạo ra nó có thể đã viết cả một luận án dựa trên dòng mã này. Nhưng trong ngành công nghiệp trò chơi điện tử, có lẽ đó chỉ là một ngày làm việc bình thường của ai đó.
Bí ẩn của 0x5f3759df
Khi đoạn mã này được công bố, nó đã gây ra một sự chấn động lớn trong giới lập trình. Các nhà khoa học máy tính đã cố gắng giải mã tại sao con số này lại cho ra kết quả xấp xỉ tốt đến vậy.
Giải thích tóm tắt
-
Chuyển đổi bit: Thuật toán này coi số dấu phẩy động (float) như một số nguyên 32-bit. Bằng cách thực hiện các phép toán bit trên số nguyên này, nó có thể ước tính giá trị logarit của số ban đầu.
-
Sử dụng Magic Number: Phép trừ với
0x5f3759dfvà dịch bit (>> 1) chính là cách để tạo ra một ước lượng ban đầu của giá trị căn bậc hai nghịch đảo một cách cực kỳ nhanh chóng. Con số này được cho là đã được tìm thấy qua quá trình thử nghiệm và tinh chỉnh tỉ mỉ. -
Lặp Newton-Raphson: Sau đó, kết quả ước lượng được cải thiện bằng một lần lặp của phương pháp Newton-Raphson, một kỹ thuật để tìm nghiệm gần đúng của một phương trình. Chỉ với một lần lặp, độ chính xác đã đủ dùng cho hầu hết các mục đích trong game.
Không chỉ xuất hiện trong Quake 3, dòng mã này còn được tìm thấy trong mã nguồn của Doom – trò chơi 3D mang tính cách mạng từ những năm 90. Phần bình luận “what the fuck?” từ John Carmack, một trong những bộ óc vĩ đại của ngành game, khiến nhiều người tin rằng ông không phải là người tạo ra nó, mà chỉ khéo léo áp dụng một công thức đã có sẵn vào đồ họa 3D – điều mà trước đó chưa ai nghĩ tới.
Di sản
Dù ngày nay các CPU và GPU hiện đại đã có các lệnh phần cứng (như rsqrtss trên x86) để tính toán căn bậc hai nghịch đảo nhanh hơn nhiều, thuật toán này vẫn là một biểu tượng của sự sáng tạo và tối ưu hóa trong lập trình.
Nó cho thấy rằng, với tư duy độc đáo, các lập trình viên có thể vượt qua những hạn chế về phần cứng để tạo ra những sản phẩm đột phá. Câu chuyện về magic number 0x5f3759df vẫn được các lập trình viên nhắc đến như một minh chứng cho sự "ma thuật" của lập trình.