C++ 빠른 역제곱근(Fast Inverse Square Root) 알고리즘 완벽 가이드

이 문제에서는 하나의 정수 x가 주어지며, 우리의 과제는 해당 값을 32비트 부동 소수점 숫자로 다루어 빠른 역제곱근(Fast Inverse Square Root)을 계산하는 것입니다.

역제곱근을 구하는 이 알고리즘은 프로그래밍 전반에서 매우 유용하게 활용됩니다. 대표적으로 3D 그래픽스나 비디오 게임 엔진에서의 벡터 정규화(vector normalization)가 있습니다. 일반적인 부동 소수점 나눗셈과 제곱근 연산보다 훨씬 빠르게 근사값을 얻을 수 있기 때문에, 성능이 중요한 실시간 렌더링 환경에서 오랫동안 사랑받아 온 기법입니다.

알고리즘 동작 원리

1단계: 부동 소수점 값을 정수로 변환합니다. 이때 IEEE 754 부동 소수점 표현 방식을 활용하여 같은 메모리를 비트 수준에서 정수로 재해석합니다.

2단계: 정수 값에 대해 연산을 수행하여 역제곱근의 근사값을 구합니다. 여기서 핵심은 마법 상수(magic constant)라고 불리는 0x5f3759df를 활용하는 것입니다.

3단계: 1단계에서 사용한 것과 동일한 방법으로 정수 값을 다시 부동 소수점 형태로 되돌립니다.

4단계: 뉴턴 방법(Newton's method)을 한 번 적용하여 근사값의 정밀도를 향상시킵니다.

알고리즘 구현 예제

다음 C++ 프로그램은 위 알고리즘이 실제로 어떻게 동작하는지 보여줍니다.

#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;
}

실행 결과

The inverse square root of the number 256 is 0.0623942

결과를 검증해 보면, 256의 제곱근은 16이므로 정확한 역제곱근 값은 1/16 = 0.0625입니다. 알고리즘이 반환한 근사값 0.0623942는 이에 매우 근접하며, 단 한 번의 뉴턴 반복만으로도 충분히 높은 정확도를 확보할 수 있음을 보여줍니다.