▲

GN⁺: 빠른 역제곱근 알고리즘에 대한 모든 지식

 (github.com/francisrstokes)
5P by neo 3달전 | favorite | 댓글 2개

빠른 역제곱근 알고리즘에 대한 모든 것

알고리즘

  • 빠른 역제곱근 알고리즘은 Quake 3 소스 코드에서 유명해진 알고리즘으로, John Carmack이 사용했음.
  • 이 알고리즘은 부동 소수점의 비트를 조작하여 역제곱근을 빠르게 계산함.
  • 코드 예시: 
    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 ); // 마법의 상수
  y = *(float*)&i;
  y = y * ( threehalfs - ( x2 * y * y ) );  // 1차 반복

  return y;
}

32비트 부동 소수점: 표현

  • IEEE-754 32비트 부동 소수점은 3개의 구성 요소로 이루어짐:
    • 부호: 1비트, 숫자의 양수/음수 여부를 나타냄.
    • 지수: 8비트, 숫자의 범위를 결정함.
    • 가수: 23비트, 범위 내에서 숫자의 위치를 지정함.
  • 실제 값은 다음과 같이 계산됨: 
    N = -1^S * 2^(E-127) * (1 + M/2^23)

32비트 부동 소수점: 비트 해석

  • 부동 소수점의 내부 표현은 일반적으로 프로그래머에게 중요하지 않음.
  • 그러나 이 표현을 잘 이해하면 효율적인 알고리즘 설계가 가능함.
  • 부동 소수점의 비트 패턴을 정수로 해석하면 로그 함수의 근사값이 됨. 
    log2(x) ≈ Ix / L - B

뉴턴 방법

  • 초기 근사값을 개선하기 위해 뉴턴 방법(Newton's method)을 사용함.
  • 뉴턴 방법은 주어진 함수의 근사값을 반복적으로 개선하는 알고리즘임.
  • 코드 예시: 
    y = y * ( threehalfs - ( x2 * y * y ) ); // 1차 반복

결론

  • 이 알고리즘은 부동 소수점 시스템의 내부 수학적 세부 사항을 깊이 이해하고, 컴퓨터에서 빠르게 실행되는 연산을 활용하여 설계됨.
  • 알고리즘의 기원은 확실하지 않지만, 매우 효율적이고 잘 설계된 엔지니어링의 예시임.

GN⁺의 의견

  • 역사적 중요성: 이 알고리즘은 당시의 하드웨어 제약을 극복하기 위해 고안된 혁신적인 방법임.
  • 교육적 가치: 부동 소수점의 내부 구조와 수학적 원리를 이해하는 데 큰 도움이 됨.
  • 현대적 적용: 현대 하드웨어에서는 덜 필요할 수 있지만, 알고리즘의 원리는 여전히 유용함.
  • 최적화 가능성: 알고리즘의 상수 값은 최적화될 수 있으며, 이는 추가 연구의 여지가 있음.
  • 비판적 시각: 현대 하드웨어에서는 더 나은 방법이 있을 수 있으므로, 항상 최신 기술과 비교해보는 것이 중요함.
▲
joyfui 3달전  [-]

잊을만하면 올라오는 신기한 코드..ㅎ

답변달기
▲
neo 3달전  [-]
Hacker News 의견

  • SSE 명령어 지원: 1999년 이후에 제작된 컴퓨터는 SSE 명령어 세트를 지원하며, _mm_rsqrt_ps 명령어를 통해 빠르게 역제곱근을 계산할 수 있음.

  • 현대 하드웨어의 발전: 현대 하드웨어에서는 역제곱근 계산이 CPU에서 빠르게 이루어질 수 있으며, GPU로 모든 부동 소수점 연산을 오프로드하는 것은 오해임.

  • MMIX 구현: MMIX 언어로 역제곱근 계산을 구현한 예시 코드가 있음. 이 코드는 원래 숫자가 2^-1021보다 크다는 가정을 함.

  • 공식의 오타: 부동 소수점 공식에 오타가 있음. (-1)^S로 수정해야 함.

  • 로그의 해석: 원시 비트 패턴을 해석하는 것은 로그의 조각별 선형 근사치가 아님. 데이터 포인트 사이의 선은 실제로 존재하지 않음.

  • 위키백과 참고: 이 함수와 그 역사에 대한 좋은 논의가 위키백과에 있음. 위키백과 링크

  • GitHub 코드 모음: 관련된 몇 가지 코드를 GitHub에 모아둠. GitHub 링크

  • StackOverflow 참고: 최적화된 저정밀도 근사치에 대한 StackOverflow 질문도 참고할 만함. StackOverflow 링크

  • 3D 엔진 최적화 경험: Quake 이전에 3D 엔진을 구축하며 최적화 경험을 쌓았고, 알고리즘 최적화가 항상 승리함.

  • 유튜브 비디오 추천: 이 주제에 대한 흥미로운 비디오가 있음. 유튜브 링크

  • 생산성 시간 도둑: 이 주제에 빠져들어 생산적인 시간을 많이 빼앗김.

  • 최적의 마법 숫자: 유명한 코드 스니펫의 마법 숫자가 최적의 상수가 아님. 더 나은 상수를 찾는 것이 가능하며, Jupyter 노트북을 통해 최적의 마법 숫자를 찾을 수 있음.

답변달기