Math & Physics
Advanced
C99 / C++ / C#
퀘이크 III의 전설적인 고속 역제곱근(Fast Inverse Square Root) 알고리즘과 원리
3D 벡터 정규화(1/sqrt(x))를 위해 부동소수점 비트 트릭(0x5f3759df)과 뉴턴-랩슨(Newton-Raphson) 근사법을 사용한 존 카맥의 전설적인 연산 기법 해설.
#Math #Algorithm #Optimization #ComputerGraphics #Quake
핵심 개념컴퓨터 그래픽스에서 3D 벡터 정규화는 $\frac{1}{\sqrt{x}}$ 연산을 수천만 번 요구합니다. FPU 나눗셈이 느리던 시절, IEEE 754 부동소수점 비트 표현을 정수로 캐스팅하여 마법의 상수
0x5f3759df로 시프트한 뒤 뉴턴 근사법 1회로 극상의 속도를 달성한 기념비적 알고리즘입니다.1. 고속 역제곱근 원본 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; // 부동소수점 비트를 정수로 해석
i = 0x5f3759df - ( i >> 1 ); // 마법의 상수와 1비트 우측 시프트
y = * ( float * ) &i; // 다시 부동소수점으로 역해석
y = y * ( threehalfs - ( x2 * y * y ) ); // 뉴턴-랩슨(Newton-Raphson) 1차 반복
return y;
}