고속 역 제곱근

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 작동 원리
4. 수학적 분석
5. 정확도 및 한계
참조

1. 개요

고속 역 제곱근(Fast inverse square root)은 제곱근의 역수를 빠르게 계산하는 알고리즘으로, 특히 3D 그래픽스 분야에서 널리 사용되었다. 이 알고리즘은 비트 조작, 매직 넘버, 뉴턴 방법을 결합하여 부동 소수점 연산을 효율적으로 수행한다. 1990년대 후반 3dfx Interactive의 그래픽 카드에서 사용되었으며, 1999년 출시된 게임 퀘이크 3 아레나에 적용되면서 널리 알려졌다. C 언어로 구현된 코드는 비트 해킹과 매직 넘버를 활용하여 초기 근사값을 구하고, 뉴턴 방법을 통해 정확도를 높인다. 이 알고리즘은 하드웨어의 발전으로 인해 현대에는 사용 빈도가 줄었지만, 알고리즘 설계의 독창성으로 인해 여전히 주목받고 있다.

2. 역사

윌리엄 카한과 K.C. 응은 1986년 5월에 비트 조작 기술과 뉴턴 반복법을 사용하여 제곱근을 계산하는 방법에 대한 미출판 논문을 작성했다.^[9] 1980년대 후반, 클리브 몰러는 Ardent Computer에서 이 기술을 접하고^[10] 동료인 그레그 월시에게 전달했다. 그레그 월시는 현재 널리 알려진 상수와 빠른 역 제곱근 알고리즘을 고안했다. 1994년경 게리 타롤리가 이 알고리즘을 3dfx Interactive에 가져왔다.^[13]^[11]

짐 블린은 1997년 ''IEEE 컴퓨터 그래픽스 앤 애플리케이션'' 칼럼에서 역 제곱근의 간단한 근사값을 제시했다. Activision의 1997년 게임 Interstate '76에서 이 알고리즘의 변형이 발견되었다.^[1]

id Software의 1999년 1인칭 슈팅 게임 ''Quake III Arena''는 이 알고리즘을 사용했다. 브라이언 훅이 3dfx에서 id Software로 알고리즘을 가져왔을 가능성이 있다.^[13] 2000년 중국 개발자 포럼 CSDN에 이 코드에 대한 논의가 게시되었고,^[18] 2002년과 2003년에는 Usenet과 gamedev.net 포럼을 통해 널리 알려졌다. 알고리즘 작성자와 상수 도출 방법에 대한 추측이 있었으며, 일부는 존 D. 카맥을 언급했다.^[11] ''Quake III'' 소스 코드는 QuakeCon 2005에서 공개되었으나, 명확한 답을 주지는 못했다. 2006년 원작자인 그레그 월시가 Slashdot의 추측이 인기를 얻자 Beyond3D에 연락하여 저작권 문제가 해결되었다.^[13]

2007년에는 이 알고리즘이 FPGA를 사용한 일부 전용 하드웨어 버텍스 셰이더에 구현되었다.^[2]

2. 1. 개발 배경

윌리엄 카한과 버클리의 K.C. 응은 1986년 5월에 비트 조작 기술과 뉴턴 반복법을 사용하여 제곱근을 계산하는 방법을 설명하는 미출판 논문을 작성했다.^[9] 1980년대 후반, 클리브 몰러는 Ardent Computer에서 이 기술을 접하고^[10] 동료인 그레그 월시에게 전달했다. 그레그 월시는 현재 유명한 상수와 빠른 역 제곱근 알고리즘을 고안했다. 1994년경, 당시 아덴트를 지원하던 회사인 쿠보타의 컨설턴트였던 게리 타롤리가 이 알고리즘을 3dfx Interactive에 도입했다.^[13]^[11]

짐 블린은 1997년 ''IEEE 컴퓨터 그래픽스 앤 애플리케이션''에서 역 제곱근의 근사 방법을 발표했다.

2. 2. ''퀘이크 3 아레나''와 대중화

1999년, id Software에서 출시한 1인칭 슈팅 게임 ''퀘이크 3 아레나''는 이 알고리즘을 사용하여 그래픽 연산 속도를 크게 향상시켰다. 브라이언 훅은 3dfx에서 id Software로 알고리즘을 가져왔을 수 있다.^[13] 2000년 중국 개발자 포럼 CSDN에 이 코드에 대한 논의가 게재되었고,^[18] 2002년과 2003년에는 Usenet과 gamedev.net 포럼을 통해 코드가 널리 퍼졌다.

알고리즘을 누가 작성했고 상수가 어떻게 파생되었는지에 대한 추측이 제기되었으며, 일부는 존 D. 카맥이라고 추측했다.^[11] ''퀘이크 3''의 전체 소스 코드는 QuakeCon 2005에서 공개되었지만, 답을 제공하지 못했다. 저작권 문제는 2006년 원작자인 그레그 월시가 Slashdot에서 추측이 인기를 얻은 후 Beyond3D에 연락하면서 해결되었다.^[13]

2. 3. 하드웨어 구현

2007년, 이 알고리즘은 FPGA를 사용하는 일부 전용 하드웨어 버텍스 셰이더에 구현되었다.^[2]

3. 작동 원리

표면 법선은 조명 및 음영 계산에 널리 사용되며, 벡터의 노름 계산이 필요하다. 그림에는 표면에 수직인 벡터 필드가 표시되어 있다.

입사각으로부터 반사각을 찾기 위해 법선 $C$ 를 사용하는 2차원 예시이다. 이 예시는 곡면 거울에서 반사되는 빛을 나타내며, 고속 역 제곱근은 이러한 계산을 3차원 공간으로 일반화하는 데 사용된다.

부동 소수점 숫자의 역 제곱근은 디지털 신호 처리에서 벡터를 정규화하여 길이를 1로 만드는 단위 벡터를 생성하는 데 사용된다.^[11] 컴퓨터 그래픽스 프로그램에서는 입사각과 반사를 계산하여 조명 및 음영 처리를 구현하는데, 이때 역 제곱근이 사용된다. 1990년대 초, 코드가 개발될 당시에는 부동 소수점 처리 성능이 정수 처리 속도보다 느렸다.^[11] 이는 변환 및 조명을 처리하는 특수 하드웨어가 나오기 전까지 3D 그래픽 프로그램에 어려움을 줬다.

벡터의 길이는 유클리드 노름으로 계산되며, 이는 벡터 구성 요소 제곱 합의 제곱근이다. 벡터의 각 구성 요소를 길이로 나누면, 같은 방향을 가리키는 단위 벡터가 된다. 3D 그래픽에서 벡터

\boldsymbol v

는

(v_1, v_2, v_3)

로 표현된다.

:

\|\boldsymbol{v}\| = \sqrt{v_1^2+v_2^2+v_3^2}

는 벡터의 유클리드 노름이다.

:

\boldsymbol{\hat{v}} = \frac{\boldsymbol{v}}{\left\|\boldsymbol{v}\right\|}

는 정규화된 (단위) 벡터이다. 위 식에

\|\boldsymbol v\|

를 대입하면 다음과 같다.

:

\boldsymbol{\hat{v}} = \frac{\boldsymbol{v}}\sqrt{v_1^2+v_2^2+v_3^2}

이는 단위 벡터를 거리 구성 요소의 역 제곱근과 관련짓는다. 따라서 다음 식을 통해

\boldsymbol{\hat{v}}

를 계산할 때 역 제곱근이 사용된다.

:

\boldsymbol{\hat{v}} = \boldsymbol{v}\, \frac{1}\sqrt{v_1^2+v_2^2+v_3^2}

여기서 분수 항이

v_1^2+v_2^2+v_3^2

의 역 제곱근이다.

당시 부동 소수점 나눗셈은 곱셈보다 연산 비용이 높았다. 제곱근 계산은 많은 나눗셈 연산을 필요로 했고, 부동 소수점 연산은 계산 비용이 컸다. 고속 역 제곱근은 단 한 번의 나눗셈으로 근삿값을 제공하여 성능 이점을 제공했다.

3. 1. 부동소수점 표현 (IEEE 754)

IEEE 754 표준의 단정밀도 부동소수점 표현 방식은 실수를 부호, 지수, 가수 부분으로 나누어 표현한다.

예를 들어, 십진수 -118.625는 다음과 같이 표현된다.

1. 음수이므로 부호(sign)는 1이다.

2.

118.625_{10}=1110110.101_{2}

이므로

118.625_{10}=(2_{10})^{110_{2}}\times 1.110110101_{2}

와 같이 소수점 앞을 1로 만든다.

3. 지수(exponent)는 음수 지수를 고려해서 127을 더한

110_{2}+1111111_{2}=10000101_{2}

가 되고, 가수(fraction)는 소수점 뒤의 23자리 11011010100000000000000가 된다.

float 양수

x

를 long 비트로 표현하면

x=2^\mathrm{E}(1+\mathrm{M})

에서

\mathrm{E}

와

\mathrm{M}

을 알 수 있고, 양변에 밑이 2인 로그를 취하면

:

\log_2(x)=\mathrm{E}+\log_2(1+\mathrm{M})

이다.

0이 아닌 실수

x

를 단정밀도 부동 소수로 인코딩하는 과정은 다음과 같다.

:

x = \pm 1.b_1b_2b_3\ldots \times 2^{e_x}

여기서 지수

e_x

는 정수이고,

1.b_1b_2b_3\ldots

는 가수(mantissa)의 이진 표현이다. 가수에서 소수점 앞의 1은 항상 존재하므로 저장할 필요가 없다. 위 식은 다음과 같이 다시 쓸 수 있다.

:

x = \pm 2^{e_x} (1 + m_x)

여기서

m_x

는

0.b_1b_2b_3\ldots

를 의미하며,

m_x \in [0, 1)

이다. 이 형식에서 세 개의 부호 없는 정수가 계산된다.

$S_x$ : 부호 비트 (1비트). $x$ 가 양수이면 0, 음수이면 1.
$E_x = e_x + B$ : 바이어스된 지수 (8비트). 여기서 $B = 127$ 는 지수 바이어스이다.
$M_x = m_x \times L$ : 가수 (23비트). 여기서 $L = 2^{23}$ 이다.

이 필드들은 왼쪽에서 오른쪽 순서로 32비트 컨테이너에 저장된다.

x

가 양의 정규수라면,

:

x = 2^{e_x} (1 + m_x)

:

\log_2(x) = e_x + \log_2(1 + m_x)

m_x \in [0, 1)

이므로, 우변의 로그는 다음과 같이 근사할 수 있다.

:

\log_2(1 + m_x) \approx m_x + \sigma

\sigma

는 근사값을 조정하는 자유 매개변수이다.

부동 소수점 숫자에 변환된 정수(파란색)를 크기가 조정되고 이동된 로그(회색)와 비교한 그림

따라서,

:

\log_2(x) \approx e_x + m_x + \sigma.

x

의 부동 소수점 비트 패턴을 정수

I_x

로 해석하면,^[6]

:

\begin{align}I_x &= E_x L + M_x\\&= L (e_x + B + m_x)\\&= L (e_x + m_x + \sigma + B - \sigma)\\&\approx L \log_2(x) + L (B - \sigma).\end{align}

즉,

\log_2(x)

는 다음과 같이 근사된다.

:

\log_2(x) \approx \frac{I_x}{L} - (B - \sigma).

3. 2. 로그 근사

컴퓨터나 계산기 없이

\frac{1}{\sqrt{x}}

를 계산하려면 로그표와 모든 밑

b

에 대해 유효한 항등식

\log_b\left(\frac{1}{\sqrt{x}}\right) = \log_b\left(x^{-\frac{1}{2}}\right) = -\frac{1}{2} \log_b(x)

이 유용하다. 고속 역 제곱근은 이 항등식과 부동 소수점을 정수로 변환하면 해당 로그의 대략적인 근사값을 얻는다는 사실에 기반한다. 방법은 다음과 같다.

만약

x

가 양의 정규수라면:

:

x = 2^{e_x} (1 + m_x)

그러면

:

\log_2(x) = e_x + \log_2(1 + m_x)

그리고

m_x \in [0, 1)

이므로 우변의 로그는 다음으로 근사할 수 있다.^[6]

:

\log_2(1 + m_x) \approx m_x + \sigma

여기서

\sigma

는 근사값을 조정하는 데 사용되는 자유 매개변수이다. 예를 들어,

\sigma = 0

은 간격의 양쪽 끝에서 정확한 결과를 생성하며,

\sigma = \frac{1}{2} - \frac{1+\ln(\ln(2))}{2\ln(2)} \approx 0.0430357

은 최적 근사값 (오차의 균일 노름의 의미에서 최적)을 생성한다. 그러나 이 값은 후속 단계를 고려하지 않으므로 알고리즘에서 사용되지 않는다.

따라서 다음과 같은 근사가 있다.

:

\log_2(x) \approx e_x + m_x + \sigma.

x

의 부동 소수점 비트 패턴을 정수

I_x

로 해석하면^[6]

:

\begin{align}I_x &= E_x L + M_x\\&= L (e_x + B + m_x)\\&= L (e_x + m_x + \sigma + B - \sigma)\\&\approx L \log_2(x) + L (B - \sigma).\end{align}

그런 다음

I_x

는 오른쪽 그림과 같이

\log_2(x)

의 크기가 조정되고 이동된 조각별 선형 근사값으로 나타난다. 즉,

\log_2(x)

는 다음으로 근사된다.

:

\log_2(x) \approx \frac{I_x}{L} - (B - \sigma).

y=\frac{1}{\sqrt{x}}

의 계산은 다음 항등식을 기반으로 한다.

:

\log_2(y) = - \tfrac{1}{2}\log_2(x)

위의 로그 근사를 사용하여

x

와

y

에 모두 적용하면 위의 방정식은 다음과 같다.

:

\frac{I_y}{L} - (B - \sigma) \approx - \frac{1}{2}\left(\frac{I_x}{L} - (B - \sigma)\right)

따라서

I_y

의 근사는 다음과 같다.

:

I_y \approx \tfrac{3}{2} L (B - \sigma) - \tfrac{1}{2} I_x

이는 코드에서 다음과 같이 작성된다.

:

i = 0x5f3759df - ( i >> 1 );

위의 첫 번째 항은 매직 넘버이다.

:

\tfrac{3}{2} L (B - \sigma) = \mathtt{0x5F3759DF}

이로부터

\sigma \approx 0.0450466

임을 추론할 수 있다. 두 번째 항인

\frac{1}{2}I_x

는

I_x

의 비트를 오른쪽으로 한 자리 이동하여 계산된다.

3. 3. 뉴턴의 방법

뉴턴의 방법을 사용하여 근사값의 정확도를 높인다. ''퀘이크 3 아레나''에서는 한 번의 뉴턴 반복만 사용되었다.^[11]

y

를 역 제곱근

\left(y = \frac{1}{\sqrt{x}}\right)

이라고 할 때,

f(y)=\frac{1}{y^2}-x=0

이다. 이전 단계에서 얻은 근사값은 근 찾기 방법을 사용하여 개선할 수 있는데, 이는 함수의 영점을 찾는 방법이다. 이 알고리즘은 뉴턴 방법을 사용한다.

y

에 대한 근사값

y_n

이 있다면, 더 나은 근사값

y_{n+1}

은

y_n - \frac{f(y_n)}{f'(y_n)}

을 계산하여 구할 수 있다. 여기서

f'(y_n)

은

y_n

에서의

f(y)

의 미분이다. 위의

f(y)

에 대해, 식은 다음과 같다.

:

y_{n+1} = \frac{y_{n}\left(3-xy_n^2\right)}{2}

(

f(y)= \frac{1}{y^2} - x

이고

f'(y) = -\frac{2}{y^3}

이다.)

y

를 부동 소수점 숫자로 취급하면 `y = y*(threehalfs - x/2*y*y);`는 다음 식과 같다.

:

y_{n+1} = y_{n}\left (\frac32-\frac{x}{2}y_n^2\right ) = \frac{y_{n}\left(3-xy_n^2\right)}{2}.

이 단계를 반복하여 함수의 출력(

y_{n+1}

)을 다음 반복의 입력으로 사용하면, 알고리즘은

y

가 역 제곱근으로 수렴하도록 한다. ''Quake III'' 엔진의 목적을 위해, 단 한 번의 반복만 사용되었다. 두 번째 반복은 코드에 남아 있었지만 주석 처리되었다.

뉴턴 방법의 속도와 정확성 측면에서 한 번의 반복과 두 번의 반복 사이의 중간 단계는 핼리 방법의 단일 반복이다. 이 경우, 핼리 방법은 시작 공식

f(y) = \frac{1}{y^{1/2}} - xy^{3/2} = 0

을 사용하여 뉴턴 방법을 적용하는 것과 동일하다. 그러면 업데이트 단계는 다음과 같다.

:

y_{n+1} = y_{n} - \frac{f(y_n)}{f'(y_n)} = y_n \left(\frac{3 + xy_n^2}{1 + 3xy_n^2}\right),

여기서 구현은 임시 변수를 통해

xy_n^2

을 한 번만 계산해야 한다.

3. 4. 코드 (C 언어)

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차 반복

// y = y * ( threehalfs - ( x2 * y * y ) ); // 2차 반복, 제거할 수 있음

return y;

}

```

이 코드는 ''퀘이크 3 아레나''에 사용된 고속 역 제곱근 계산 코드로, C 전처리기 지시문은 제거되었지만 원래 주석은 그대로 포함되어 있다.^[23] 1990년대 초에는 역 제곱근을 계산하기 위해 순람표를 사용하는 것이 일반적이었지만, 이 코드는 순람표보다 빠르고 다른 일반적인 알고리즘보다 4배 정도 빨랐다.^[24]

코드의 핵심 부분은 다음과 같다.

`i = * ( long * ) &y;`: 부동 소수점 수 `y`의 비트 패턴을 정수형 `i`로 해석한다. (부동 소수점 비트 레벨 해킹)
`i = 0x5f3759df - ( i >> 1 );`: 매직 넘버 `0x5f3759df`를 사용하여 비트 연산을 수행한다. (이게 뭐지?)
`y = * ( float * ) &i;`: 정수형 `i`의 비트 패턴을 다시 부동 소수점 수 `y`로 해석한다.
`y = y * ( threehalfs - ( x2 * y * y ) );`: 뉴턴의 방법을 1회 반복하여 정확도를 높인다.

이 알고리즘은 뉴턴의 방법을 사용하여 비교적 정확한 결과를 만들어 내지만, 소수점 손실 때문에 부정확하고 1999년에 출시된 x86 SSE의 `rsqrtss`에 비해 훨씬 느리다.^[24] 또한 `long`을 사용하는 것은 64비트 시스템에서 코드의 이식성을 떨어뜨릴 수 있다.

C 표준에 따르면, 부동 소수점 값을 정수로 변환한 다음 해당 포인터를 역참조하여 해석하는 것은 정의되지 않은 동작이다. 이를 피하기 위해 다음과 같은 방법을 사용할 수 있다.

```c

#include // uint32_t

float Q_rsqrt(float number)

{

union {

float f;

uint32_t i;

} conv = { .f = number };

conv.i = 0x5f3759df - (conv.i >> 1);

conv.f *= 1.5F - (number * 0.5F * conv.f * conv.f);

return conv.f;

}

```

공용체를 사용하여 부동 소수점 값과 정수 값을 같은 메모리 공간에 저장하여 비트 패턴을 해석하는 방법이다. 그러나 타입 펀닝을 공용체를 통해 사용하는 것도 C++에서는 정의되지 않은 동작이다.

최신 C++에서는 `std::bit_cast`를 사용하여 이 함수의 캐스트를 구현하는 것이 바람직하다.

```c++

import std;

constexpr std::float32_t Q_rsqrt(std::float32_t number) noexcept

{

const auto y = std::bit_cast(

0x5f3759df - (std::bit_cast(number) >> 1));

return y * (1.5f32 - (number * 0.5f32 * y * y));

}

4. 수학적 분석

근사 오차를 최소화하는 함수를 개발하여 마법 숫자가 선택되었다. 크리스 로몬트는 선형 근사 단계에 대한 최적의 상수를 0x5F37642F로 계산했는데, 이는 0x5F3759DF에 가깝지만, 이 새로운 상수는 뉴턴 방법의 한 번의 반복 이후 약간 덜 정확했다.^[17] 로몬트는 이후 한 번과 두 번의 뉴턴 반복 후에도 최적인 상수를 찾기 위해 검색했고, 모든 반복 단계에서 원래보다 더 정확한 0x5F375A86을 발견했다.^[17] 그는 원래 상수의 정확한 값이 유도 또는 시행착오를 통해 선택되었는지에 대해 질문했다.^[17] 로몬트는 64비트 IEEE754 크기의 double 자료형에 대한 마법 숫자는 0x5FE6EC85E7DE30DA라고 말했지만, 나중에 매튜 로버트슨에 의해 정확히 0x5FE6EB50C7B537A9임이 밝혀졌다.^[17]

얀 카들렉은 단일 뉴턴 방법 반복의 상수를 조정하여 상대 오차를 2.7배 더 줄였다.^[7] 그는 전수 조사를 거쳐 다음 코드를 통해 결과를 얻었다.

```

conv.i = 0x5F1FFFF9 - ( conv.i >> 1 );

conv.f *= 0.703952253f * ( 2.38924456f - x * conv.f * conv.f );

return conv.f;

```

이제 단정밀도 부동소수점 숫자에 대한 마법 숫자를 결정하기 위한 완전한 수학적 분석이 가능해졌다.^[8]

5. 정확도 및 한계

오른쪽 그래프는 뉴턴의 방법을 한 번 사용하여 개선된 오차를 보여준다. 0.01에 대해 표준 라이브러리는 10.0을, 위 알고리즘을 적용한 함수는 9.982522를 반환하며, 로그 스케일에서 서로의 차이는 일정한 영역을 벗어나지 않는다. Chris Lomont는 더 정확하게 근사하는 매직 넘버 0x5f375a86을, Matthew Robertson은 배정밀도 표현에서 유효한 매직 넘버 0x5fe6eb50c7b537a9를 찾아냈다.^[25]

부동 소수점 숫자의 역 제곱근은 벡터를 정규화하여 길이를 1로 조정하여 단위 벡터를 생성하기 위해 디지털 신호 처리에 사용된다. 예를 들어, 컴퓨터 그래픽스 프로그램은 역 제곱근을 사용하여 입사각과 반사를 조명 및 음영 처리에 대해 계산한다.

벡터의 길이는 해당 유클리드 노름을 계산하여 결정된다. 즉, 벡터 구성 요소의 제곱 합의 제곱근이다. 벡터의 각 구성 요소를 해당 길이로 나누면, 새로운 벡터는 같은 방향을 가리키는 단위 벡터가 된다. 3D 그래픽 프로그램에서 모든 벡터는 3차원 공간에 있으므로

\boldsymbol v

는 벡터

(v_1, v_2, v_3)

가 된다.

:

\|\boldsymbol{v}\| = \sqrt{v_1^2+v_2^2+v_3^2}

는 벡터의 유클리드 노름이다.

:

\boldsymbol{\hat{v}} = \frac{\boldsymbol{v}}{\left\|\boldsymbol{v}\right\|}

는 정규화된 (단위) 벡터이다.

\|\boldsymbol v\|

를 대입하면, 이 방정식은 다음과 같이 쓸 수도 있다.

:

\boldsymbol{\hat{v}} = \frac{\boldsymbol{v}}\sqrt{v_1^2+v_2^2+v_3^2}

는 단위 벡터를 거리 구성 요소의 역 제곱근과 관련시킨다. 역 제곱근은 이 방정식이 다음 방정식과 동일하기 때문에

\boldsymbol{\hat{v}}

를 계산하는 데 사용될 수 있다.

:

\boldsymbol{\hat{v}} = \boldsymbol{v}\, \frac{1}\sqrt{v_1^2+v_2^2+v_3^2}

여기서 분수 항은

v_1^2+v_2^2+v_3^2

의 역 제곱근이다.

당시 부동 소수점 나눗셈은 일반적으로 곱셈보다 비용이 많이 들었다. 고속 역 제곱근 알고리즘은 나눗셈 단계를 우회하여 성능상의 이점을 제공했다.

위에서 언급했듯이, 근사값은 매우 정확하다. 오른쪽 그래프는 0.01부터 시작하는 입력에 대한 함수의 오차(즉, 뉴턴 방법을 한 번 반복 실행하여 개선된 후의 근사 오차)를 나타낸다. 여기서 표준 라이브러리는 10.0을 결과로 제공하고, InvSqrt()는 9.982522를 제공하여 상대 오차가 0.0017478, 즉 참값 10의 0.175%가 된다. 절대 오차는 그 이후로만 감소하며 상대 오차는 모든 차수에서 동일한 경계 내에 유지된다.

하드웨어 제조업체들의 후속 추가로 인해 이 알고리즘은 대부분 쓸모없게 되었다. 예를 들어, x86에서 인텔은 1999년에 SSE 명령어 `rsqrtss`를 도입했다. 인텔 코어 2에 대한 2009년 벤치마크에서 이 명령어는 1 플로트당 0.85ns가 소요되었는데, 이는 고속 역 제곱근 알고리즘의 3.54ns에 비해 더 적은 오차를 보였다.^[14]

일부 저가형 임베디드 시스템에는 특수 제곱근 명령어가 없다. 그러나 이러한 시스템의 제조업체는 일반적으로 CORDIC과 같은 알고리즘을 기반으로 하는 삼각 함수 및 기타 수학 라이브러리를 제공한다.

참조

_[1] 웹사이트 Fast reciprocal square root... in 1997?! https://inbetweennam[...] 2021-06-01
_[2] 서적 2014 International Conference on Advances in Electrical Engineering (ICAEE) 2014-01
_[3] 문서 Use of the type long reduces the portability of this code on modern systems. For the code to execute properly, [[sizeof]](long) must be 4 bytes, otherwise negative outputs may result. Under many modern 64-bit systems, [[sizeof]](long) is 8 bytes. The more portable replacement is int32_t.
_[4] 문서 $E_x$ should be in the range $[1, 254]$ for $x$ to be representable as a [[Normal number (computing)|normal number]].
_[5] 문서 The only real numbers that can be represented ''exactly'' as floating point are those for which $M_x$ is an integer. Other numbers can only be represented approximately by rounding them to the nearest exactly representable number.
_[6] 문서 Since $x$ is positive, $S_x = 0$ .
_[7] personal blog Řrřlog::Improving the fast inverse square root http://rrrola.wz.cz/[...] 2020-12-14
_[8] 간행물 Elementary Functions and Approximate Computing https://ieeexplore.i[...] 2020-12
_[9] 웹사이트 sqrt implementation in fdlibm - See W. Kahan and K.C. Ng's discussion in comments in lower half of this code http://www.netlib.or[...]
_[10] 웹사이트 Symplectic Spacewar http://blogs.mathwor[...] MATLAB 2012-06-19
_[11] 웹사이트 Origin of Quake3's Fast InvSqrt() http://www.beyond3d.[...] 2009-02-12
_[12] 웹사이트 quake3-1.32b/code/game/q_math.c https://github.com/i[...] id Software 2017-01-21
_[13] 웹사이트 Origin of Quake3's Fast InvSqrt() - Part Two http://www.beyond3d.[...] Beyond3D 2006-12-19
_[14] 웹사이트 Timing square root http://assemblyrequi[...] 2015-05-07
_[15] 웹사이트 z88dk is a collection of software development tools that targets the 8080 and z80 computers. https://github.com/z[...]
_[16] 웹사이트 Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs http://www.agner.org[...] 2017-09-08
_[17] 웹사이트 A Brief History of InvSqrt https://mrober.io/pa[...] UNBSJ 2012-04-24
_[18] 웹사이트 Discussion on CSDN http://bbs.csdn.net/[...]
_[19] 웹사이트 Notable Properties of Specific Numbers https://mrob.com/pub[...]
_[20] 웹인용 Discussion on CSDN http://bbs.csdn.net/[...]
_[21] 웹인용 Origin of Quake3's Fast InvSqrt() http://www.beyond3d.[...] 2009-02-12
_[22] 웹인용 Origin of Quake3's Fast InvSqrt() - Part Two http://www.beyond3d.[...] Beyond3D 2006-12-19
_[23] 웹인용 quake3-1.32b/code/game/q_math.c https://github.com/i[...] id Software 2017-01-21
_[24] 웹인용 Timing square root http://assemblyrequi[...] 2015-05-07
_[25] 웹인용 A Brief History of InvSqrt https://cs.uwaterloo[...] UNBSJ 2017-11-28

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com