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

> Clean Markdown view of GeekNews topic #15157. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=15157](https://news.hada.io/topic?id=15157)
- GeekNews Markdown: [https://news.hada.io/topic/15157.md](https://news.hada.io/topic/15157.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-06-03T20:33:57+09:00
- Updated: 2024-06-03T20:33:57+09:00
- Original source: [github.com/francisrstokes](https://github.com/francisrstokes/githublog/blob/main/2024%2F5%2F29%2Ffast-inverse-sqrt.md)
- Points: 5
- Comments: 2

## Topic Body

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

#### 알고리즘

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

#### 결론

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

### GN⁺의 의견

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

## Comments



### Comment 25902

- Author: joyfui
- Created: 2024-06-03T20:56:27+09:00
- Points: 1

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

### Comment 25900

- Author: neo
- Created: 2024-06-03T20:33:58+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=40544716) 
- **SSE 명령어 지원**: 1999년 이후에 제작된 컴퓨터는 SSE 명령어 세트를 지원하며, _mm_rsqrt_ps 명령어를 통해 빠르게 역제곱근을 계산할 수 있음.

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

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

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

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

- **위키백과 참고**: 이 함수와 그 역사에 대한 좋은 논의가 위키백과에 있음. [위키백과 링크](https://en.wikipedia.org/wiki/Fast_inverse_square_root)

- **GitHub 코드 모음**: 관련된 몇 가지 코드를 GitHub에 모아둠. [GitHub 링크](https://github.com/ncruces/fastmath/blob/main/fast.go)

- **StackOverflow 참고**: 최적화된 저정밀도 근사치에 대한 StackOverflow 질문도 참고할 만함. [StackOverflow 링크](https://stackoverflow.com/questions/32042673/optimized-low-accuracy-approximation-to-rootnx-n)

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

- **유튜브 비디오 추천**: 이 주제에 대한 흥미로운 비디오가 있음. [유튜브 링크](https://www.youtube.com/watch?v=p8u_k2LIZyo)

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

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