한양과기고 에듀테크 수업도구 대시보드

⚡ 고속 역제곱근 Fast Inverse Square Root

1999년 게임 Quake III Arena의 소스 코드에서 발견된 전설적인 함수. 나눗셈도 제곱근 함수도 쓰지 않고, 비트를 정수로 훔쳐본 뒤 마법의 상수 0x5F3759DF를 빼는 것만으로 1/√x 를 눈 깜짝할 새에 계산한다. 3D 그래픽에서 벡터를 정규화(길이 1로 만들기)할 때 1/√(x²+y²+z²) 가 픽셀마다 수백만 번 필요했기 때문이다.

CODE 그 유명한 원본 (주석까지 그대로)

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 level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st Newton iteration
    // y  = y * ( threehalfs - ( x2 * y * y ) );  // 2nd iteration, can be removed

    return y;
}

핵심은 딱 두 줄이다. i = *(long*)&y 로 float의 비트 패턴을 정수로 그대로 읽고, 0x5f3759df - (i >> 1) 로 지수를 절반·부호 반전한 근사값을 만든 다음, 뉴턴법 한 번으로 다듬는다.

WHY 왜 되는가 — float은 이미 "로그자"다

IEEE 754 float32 는 부호 1비트, 지수 E 8비트, 가수 M 23비트로 x = 2^E−127(1+m) (m = M/2²³) 를 나타낸다. 비트를 정수로 읽으면 그 값은 I = 2²³·E + M 이고, 약간의 계산을 거치면

log2(x) ≈ (I / 223) − 127 + σ      // σ ≈ 0.0450 보정항

즉 정수 비트 I 자체가 log2(x) 에 거의 비례한다. 우리가 원하는 건 y = x^−1/2, 양변에 log를 씌우면 log2(y) = −½·log2(x). 로그 세계에서 −½ 곱하기는 정수 세계에서 −(I >> 1) 한 방이면 되고, 남는 상수항을 전부 뭉친 것이 바로 0x5F3759DF = 1597463007 이다.

마법의 상수는 유일하지 않다. 원본은 0x5F3759DF 지만, Chris Lomont 는 최대 상대오차를 더 줄이는 0x5F375A86 를 찾아냈다. "적당히 좋은" 상수의 넓은 골짜기가 존재한다.

TRY 직접 넣어보기 — 비트가 어떻게 변하나

x =

① 입력 x 의 비트 (정수로 재해석 전)

② 0x5F3759DF - (i >> 1) 이후의 비트 (근사 결과 y₀)

부호 (1) 지수 E (8) 가수 M (23)

단계	y 값	정확한 1/√x 대비 상대오차

ERROR 뉴턴 반복 횟수별 상대오차

비트 트릭만 쓴 y₀ 는 최대 ~3.4% 오차. 뉴턴법 y ← y(1.5 − 0.5·x·y²) 를 1번 돌리면 ~0.17%, 2번이면 ~5×10⁻⁶ 로 떨어진다. 게임에는 1번이면 충분했다.

NOW 지금도 쓸까?

안 쓴다. 요즘 CPU/GPU 에는 rsqrtss(x86 SSE), FRSQRTE(ARM) 같은 역제곱근 근사 전용 하드웨어 명령이 있어서 1~2 사이클이면 끝나고 더 정확하다. 이 함수는 "하드웨어가 느리던 시절, 수의 표현 방식(부동소수점 구조)을 꿰뚫어 본 사람이 어떤 마법을 부릴 수 있는지" 보여주는 역사적 상징으로 남았다.

비슷한 아이디어: 로그·지수·삼각함수도 "비트를 정수로 보고 다항식으로 보정"하는 근사식들이 있다. CORDIC, 부동소수점 표현 도 함께 보면 좋다.