Fast Inverse Square Root ใน C++

Fast Inverse Square Root

อัลกอริทึมที่มีชื่อเสียงในการคำนวณ 1/√x ประมาณการอย่างรวดเร็ว ใช้ในกราฟิก 3D และเกม (เช่น Quake III Arena)

ขั้นตอนของอัลกอริทึม

แปลง float เป็น integer (bit representation)
ใช้ Magic Number 0x5f3759df และ Right Shift 1 bit
แปลงกลับเป็น float
ปรับปรุงความแม่นยำด้วย Newton's Method หนึ่งรอบ

โปรแกรมตัวอย่าง

#include <iostream>
using namespace std;

float calcInvSqRoot(float n) {
    const float threehalfs = 1.5F;
    float y = n;
    long i = *reinterpret_cast<long*>(&y); // bit-level hack
    i = 0x5f3759df - (i >> 1);
    y = *reinterpret_cast<float*>(&i);
    y = y * (threehalfs - (n * 0.5F * y * y)); // Newton iteration
    return y;
}

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

ผลลัพธ์

The inverse square root of the number 256 is 0.0623942

หมายเหตุ

โค้ดต้นฉบับใช้ type-punning ผ่าน pointer ซึ่งใน C++ สมัยใหม่ควรใช้ std::bit_cast (C++20) หรือ memcpy เพื่อหลีกเลี่ยง Undefined Behavior