Nghịch đảo căn bậc 2 nhanh (Fast inverse square root) trong C++

Cho số nguyên x. Nhiệm vụ: tính nghịch đảo căn bậc 2 nhanh của số thực 32-bit.

Thuật toán nổi tiếng dùng trong đồ họa 3D, chuẩn hóa vector trong game.

Thuật toán:

1. Chuyển float sang integer (bit reinterpret).
2. Thao tác trên integer để xấp xỉ nghịch đảo căn bậc 2.
3. Chuyển ngược integer sang float.
4. Cải thiện độ chính xác bằng phép Newton.

Chương trình minh họa

Ví dụ

#include <iostream>
using namespace std;

float calcInvSqRoot(float n) {
    const float threehalfs = 1.5F;
    float y = n;
    long i = * ( long * ) &y;
    i = 0x5f3759df - ( i >> 1 );
    y = * ( float * ) &i;
    y = y * ( threehalfs - ( (n * 0.5F) * y * y ) );
    return y;
}

int main() {
    int n = 256;
    float invSqRoot = calcInvSqRoot(n);
    cout << "The inverse square root of the number " << n << " is " << invSqRoot;
    return 0;
}

Kết quả

The inverse square root of the number 256 is 0.0623942