더 빠른 asin() 함수가 바로 눈앞에 있었다

TL;DR Highlight

개발자가 raytracer 최적화를 위해 Taylor 급수와 Padé 근사로 asin() 함수를 직접 구현하려다가, 1960년대 수학 교재와 NVIDIA CG 라이브러리에 이미 최적화된 공식이 존재했음을 발견했다.

Who Should Read

그래픽스, 게임 엔진, 레이트레이싱 등 수치 연산 성능이 중요한 C++ 개발자. 또는 수학 함수의 근사(approximation) 최적화 기법을 실무에 적용해보고 싶은 개발자.

Core Mechanics

PSRayTracing(C++ 레이트레이서 프로젝트)를 프로파일링했더니 std::asin() 호출이 병목으로 나타났고, 이를 근사 함수로 대체해 성능을 높이려는 시도가 시작됐다.
먼저 Taylor 급수(어떤 함수를 다항식의 합으로 표현하는 수학적 기법) 4차 근사를 직접 구현했고, x가 -0.8~0.8 범위 안에서는 잘 동작했지만 그 범위 밖에서는 오차가 커서 결국 범위 밖에서는 std::asin()으로 fallback하는 방식을 사용했다. 이 방법으로 약 5% 속도 향상을 얻었다.
다음으로 Padé Approximant(Taylor 급수를 분수 형태의 다항식으로 변환해 더 넓은 범위에서 정확도를 높이는 기법)를 Python으로 계산해 적용했지만, 오히려 표준 라이브러리보다 느려서 실패했다.
막힌 상황에서 LLM에게 질문했더니, Stack Overflow에 올라온 NVIDIA CG 라이브러리 기반의 fast_asin 코드를 알려줬다. 알고 보니 이 코드는 1955년 Hastings의 수치해석 교재와 Abramowitz & Stegun 수학 공식 모음집(4.4.45번 공식)에 이미 수록된 내용이었다.
해당 NVIDIA CG 기반 근사 공식은 square root를 활용한 구조로 되어 있으며, 최종적으로 이 코드를 C++에 적용했더니 약 90% 속도 향상(1.9배)이라는 큰 개선을 얻었다. 이전의 Taylor 급수 5% 향상과 비교하면 압도적인 차이다.
LLM이 알려준 코드의 출처를 추적했더니 7년 된 Stack Overflow 답변이었고, 그 답변은 다시 1960년대 수학 교재로 이어졌다. 저자는 '처음부터 직접 찾아봤으면 훨씬 빨리 해결됐을 것'이라고 자평했다.
이 경험의 핵심 교훈은 '수치 함수 최적화는 이미 수십 년간 연구가 쌓인 분야이므로, Taylor 급수 같은 200년 된 기법보다 minimax 근사나 Remez 알고리즘 같은 현대적 기법을 먼저 찾아보는 것이 낫다'는 것이다.

Evidence

댓글에서 수치 근사 분야 배경이 있는 사람들이 Taylor 급수는 근사 함수 구현에 좋지 않은 선택이라고 지적했다. Padé Approximant도 Taylor 급수를 기반으로 하면 효과가 제한되고, 차라리 원래 함수에 직접 Chebyshev 근사나 Remez 알고리즘을 적용하는 것이 minimax(최대 오차를 최소화) 관점에서 훨씬 낫다는 의견이 있었다.
저자가 '60년대 수학 교재'라고 표현한 Abramowitz & Stegun 공식 모음집이 실제로는 수치해석 분야에서 Knuth의 'The Art of Computer Programming'에 준하는 권위 있는 레퍼런스라는 점을 댓글러들이 지적했다. 이 책이 obscure한 텍스트가 아니라는 점을 모르고 넘어간 것이 저자의 실수라는 뉘앙스의 댓글이 있었다.
빠른 asin()의 진짜 출처를 추적한 댓글이 있었는데, 1955년 Hastings의 'Approximations for Digital Computers'(Princeton) 159~163페이지가 원조이며, 이후 Abramowitz & Stegun이 허가를 받아 수록했고, NVIDIA CG 라이브러리가 이를 코드로 옮긴 것이라는 계보가 밝혀졌다. 원래 목적도 1950년대 컴퓨터의 성능에 맞는 효율적인 연산이었다.
알고리즘 근사보다 SIMD(한 번의 명령어로 여러 데이터를 동시 처리하는 CPU 기능)나 GPU 병렬화를 먼저 고려하는 것이 우선순위 면에서 더 낫다는 의견도 있었다. 1.05~1.90배 속도 향상도 좋지만, 16배 향상을 줄 수 있는 SIMD를 먼저 검토해야 한다는 것이다. Intel AVX-512에 `_mm512_asin_ps` intrinsic이 있다는 정보도 제공됐다.
LLM이 답을 찾아준 것에 대해 '결국 7년 된 Stack Overflow 답변을 가져온 것'이라는 냉소적인 댓글이 있었고, 실제로 해당 Stack Overflow 링크(https://stackoverflow.com/a/26030435)가 이 글이 올라오기 전 'fast asin'을 검색하면 첫 번째 결과로 나왔다는 점을 지적하며, 처음부터 검색만 했어도 됐다는 의견이 있었다.

How to Apply

C++/C 그래픽스 코드에서 std::asin() 호출이 프로파일링 병목으로 잡히는 경우, NVIDIA CG 라이브러리 기반의 fast_asin 공식(Stack Overflow: https://stackoverflow.com/a/26030435 참고)을 적용하면 별도의 복잡한 수학 없이 약 1.9배 속도 향상을 즉시 얻을 수 있다.
수치 함수(sin, cos, atan2 등)를 직접 근사 구현하려는 경우, Taylor 급수부터 시작하지 말고 Robin Green의 'Faster Math Functions' 자료(GDC 발표 포함)나 Abramowitz & Stegun 공식 모음집을 먼저 확인하면 수십 년간 검증된 minimax 근사 공식을 바로 활용할 수 있다.
새로운 수학 근사 함수 최적화를 시작하기 전에, 먼저 목표 범위(예: [-1, 1])에서 오차 파형(error waveform)을 그려보고 minimax 특유의 등진동(equioscillation) 형태가 나타나는지 확인하는 것이 좋다. 이 형태가 없으면 아직 최적화 여지가 있다는 신호이며, Remez 알고리즘(최적 다항식 근사를 생성하는 알고리즘) 도구를 사용하면 더 나은 계수를 자동으로 구할 수 있다.

Code Example

snippet

// NVIDIA CG 라이브러리 기반 fast_asin (Stack Overflow: https://stackoverflow.com/a/26030435)
// 원출처: Hastings 1955 / Abramowitz & Stegun 4.4.45
float fast_asin(float x) {
    float negate = float(x < 0);
    x = abs(x);
    float ret = -0.0187293f;
    ret *= x;
    ret += 0.0742610f;
    ret *= x;
    ret -= 0.2121144f;
    ret *= x;
    ret += 1.5707288f;
    ret = 3.14159265358979f * 0.5f - sqrt(1.0f - x) * ret;
    return ret - 2 * negate * ret;
}

// Taylor 급수 기반 4차 근사 (저자 직접 구현, ~5% 향상, -0.8 ~ 0.8 범위만 유효)
double _asin_approx_private(const double x) {
    if ((x < -0.8) || (x > 0.8)) {
        return std::asin(x); // fallback
    }
    constexpr double a = 0.5;
    constexpr double b = a * 0.75;
    constexpr double c = b * (5.0 / 6.0);
    constexpr double d = c * (7.0 / 8.0);
    const double aa = (x * x * x) / 3.0;
    const double bb = (x * x * x * x * x) / 5.0;
    const double cc = (x * x * x * x * x * x * x) / 7.0;
    const double dd = (x * x * x * x * x * x * x * x * x) / 9.0;
    return x + (a * aa) + (b * bb) + (c * cc) + (d * dd);
}

Terminology

Taylor 급수함수를 한 점 주변에서 다항식의 무한합으로 표현하는 수학 기법. 항 수를 늘릴수록 정확해지지만 계산량도 늘어나며, 입력 범위가 넓어지면 오차가 급격히 커지는 단점이 있다.

Padé ApproximantTaylor 급수를 두 다항식의 비(분수) 형태로 변환한 근사 방법. 같은 차수에서 Taylor 급수보다 더 넓은 범위에서 정확하다고 알려져 있지만, Taylor 급수 기반으로 만들면 효과가 제한된다.

minimax 근사특정 구간에서 함수 근사의 최대 오차를 최소화하는 최적 근사 방법. 오차 그래프가 등진동(equioscillation) 형태를 보이면 minimax에 가깝다는 신호다.

Remez 알고리즘minimax 의미에서 최적인 다항식 근사를 자동으로 계산해주는 수치 알고리즘. 직접 계수를 손으로 구하지 않아도 최적값을 찾아준다.

Abramowitz & Stegun1964년 미국 표준국에서 발간한 수학 함수 공식·수치 모음집. 수치해석 분야에서 바이블 수준의 레퍼런스로, 수치 근사 공식의 상당수가 이 책에 수록되어 있다.

SIMDSingle Instruction Multiple Data의 약자. CPU가 한 번의 명령으로 여러 데이터를 동시에 처리하는 기술로, 잘 활용하면 스칼라 연산 대비 수십 배 속도를 낼 수 있다.